关于leetcode:LeetCode刷题计划Day-4查找算法简单

46次阅读

共计 1268 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：

找出数组中反复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。

示例 1：
```
 输出：[2, 3, 1, 0, 2, 5, 3]
输入：2 或 3 
```
限度：
- 2 <= n <= 100000

解题思路：

遍历数组，用哈希表存储呈现过的数字：

func findRepeatNumber(nums []int) int {
    var res int
    existed := make(map[int]struct{}, len(nums)) // Go 语言空构造体不占空间；容量是确定的，能够在初始化时分配内存，节约工夫
    for _, i := range nums {if _, ok := existed[i]; ok {
            res = i
            break
        } else {existed[i] = struct{}{}
        }
    }
    return res
}

题目形容：

统计一个数字在排序数组中呈现的次数。

示例 1：
```
 输出: nums = [5,7,7,8,8,10], target = 8
输入: 2
```
示例 2：
```
 输出: nums = [5,7,7,8,8,10], target = 6
输入: 0
```
提醒：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递加数组
- -109 <= target <= 109

解题思路：

同上题，应用哈希表保留数字呈现次数：

func search(nums []int, target int) int {existed := make(map[int]int, len(nums))
    for _, i := range nums {existed[i]++
    }
    if res, ok := existed[target]; ok {return res}
    return 0
}

题目形容：

一个长度为 n - 1 的递增排序数组中的所有数字都是惟一的，并且每个数字都在范畴 0～n- 1 之内。在范畴 0～n- 1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1：
```
 输出: [0,1,3]
输入: 2
```
示例 2：
```
 输出: [0,1,2,3,4,5,6,7,9]
输入: 8
```
限度：
- 1 <= 数组长度 <= 10000

解题思路：

输出是有序的，能够采纳二分法查找第一个值不等于索引的元素：

func missingNumber(nums []int) int {return binarySearchMissing(nums, 0, len(nums)-1)
}

func binarySearchMissing(nums []int, left, right int) int {
    if left > right {return left}
    mid := left + (right-left)/2
    if nums[mid] == mid {return binarySearchMissing(nums, mid+1, right)
    } else {return binarySearchMissing(nums, left, mid-1)
    }
}

正文完