题目
数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 复制代码
分析
与查找相关的题目，一般都可以使用遍历求解，而且可能还会需要嵌套遍历，不过这类题目大多可以使用 hash 表来进行空间换时间的优化，将已遍历的值作为key值存储起来，后续遍历中遇到相同的key，那么就找到重复值了，实现如下：
实现
function findRepeatNumber(nums: number[]): number { const map:Map<number, number> = new Map() for(let i = 0; i < nums.length; i ++) { const val = nums[i] if (map.has(val)) { return val } else { map.set(val, i) } } }; 复制代码
题目
在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例：
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 复制代码
分析一
该题目算是直接做的思路比较简单，定义一个变量存储数字出现的次数，然后遍历数组，只要数字等于目标值的时候就加1，最后将结果返回即可
实现
function search(nums: number[], target: number): number { let result: number = 0 for (let i = 0; i < nums.length; i ++) { if (nums[i] === target) { result ++ } } return result }; 复制代码
分析二
做完解法一，我们发现，由所给的数组是一个排序数组，那么我们很多时候并不需要完全遍历数组就可以给出结果，我们可以根据这个特点来优化一下
既然是有序，那我们就可以使用二分查找了，定义左右端点，每次都看一下中间值的大小，
如果中间值大于目标值，则把右端点指向中间点，
如果中间值小于目标值，则把左端点指向中间点
当中间点等于目标值时，说明我们找到了目标值区域的索引
后面只要通过这个索引分别向左右扩展查找重复值即可得出结果
这样的实现查找效率为O(logN)
实现
function search(nums: number[], target: number): number { let result: number = 0 let left: number = - 1 let right: number = nums.length while(left + 1 !== right) { const mid = (left + right) >> 1 if (nums[mid] > target) { right = mid } else { left = mid } } // left 就是目标值附近的点 let index = left while(nums[index] === target) { result ++ index -- } index = left + 1 while(nums[index] === target) { result ++ index ++ } return result }; 复制代码
题目
0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例：
输入: [0,1,3] 输出: 2 复制代码
分析
抓住关键字眼有序，那么就考虑是否可以使用二分查找
观察二分查找所找的中点值与我们所求的答案有什么关系
可以发现，如果数组不缺失元素，那么中点的数值就会等于中点的索引值
那这就好办了，我们只要把问题转化为，找到中点数值不等于索引值的边界点，那么边界点加1就得到我们所找的缺失的那个值了
实现
function missingNumber(nums: number[]): number { let left: number = -1 let right: number = nums.length while(left + 1 !== right) { const mid: number = (left + right) >> 1 if (nums[mid] > mid) { right = mid } else { left = mid } } return left + 1 };
