题目描述：
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
思路(伪)：
笨笨一般上来都想双循环，啊原来我就是笨笨。。。。
果不其然超时了。
class Solution {
public:
int findRepeatNumber(vector& nums) {
vector a(nums);
int temp=0;
for(int i=0;i
优化思路：先排序再进行一次循环
class Solution {
public:
int findRepeatNumber(vector& nums) {
int temp;
sort(nums.begin(),nums.end());
for(int i=0;i
反思： 第一次运行时又出现了下标越界的情况，原因在于把i循环条件设计成了i
No. 09 在排序数组中查找数字 I
问题描述：统计一个数字在排序数组中出现的次数
示例：
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
思路：提目所给数组为升序序列，首先应当想到折半(二分）查找，通过调整边界，找到最左边target左边的元素l，再找到最右边target右边的元素r，l-r-1即为目标值
代码：
class Solution {
public:
int search(vector& nums, int target) {
int i = 0, j = nums.size() - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] <= target) i = m + 1;
else j = m - 1;
}
int right = i;
if(j >= 0 && nums[j] != target) return 0;
i = 0; j = nums.size() - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] < target) i = m + 1;
else j = m - 1;
}
int left = j;
return right - left - 1;
}
};
No. 10 0～n-1中缺失的数字
问题描述：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例：
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
思路：注意每个数与对应下表的关系，若不一致，则为要找的数 ，此外本题还可用二分，但是我懒了。
代码：
class Solution {
public:
int missingNumber(vector& nums) {
int n=nums.size()-1;
int i=0;
for (vector::iterator it = nums.begin(); it != nums.end(); it++) {
if((*it)==i) i+=1;
else break;
}
return i;
}
};
