剑指 Offer——面试题 3-2

题目

不修改数组找出重复的数字

在一个长度位n + 1的数组里的所有数字都在1 ~ n的范围内，所以数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组

输入样例

1	[2, 3, 5, 4, 3, 2, 6, 7]

输出样例

2 或 3

思路

这道题比较特殊的点就是不允许改变输入数组，如果不改变输入数组的话，我们就不能对数组进行排序，也不能交换数组元素，所以面试题 3-2 中的方法就不能用了

那我们如何找到数组中的重复元素呢？可以考虑二分的思想

因为数组是从1 ~ n的长度为n + 1的数组，所以数组中一定存在重复元素，我们先取数组的值的中点mind = 1 + n >> 1，随后我们统计数组中<= mid的元素个数，如果数量大于mid - l（左边界），说明重复元素在左边，否则说明重复元素在右边，不断的二分，我们最后就会找到这个重复出现的元素！代码如下：

代码

public:
    int duplicateInArray(vector<int>& nums) {
    	int l = 1, r = nums.size() - 1;
    	
    	while (l < r) {
    	    int mid = l + r >> 1;
    	    int s = 0;
    		for (auto num : nums) {
    			if (num <= mid && num >= l) ++s;
    		}
    		if (s > (mid - l + 1)) r = mid;
    		else l = mid + 1;
    	}
    	return l;
    }
};