Leetcode287. Find the Duplicate Number Follow up

题目：

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

• You must not modify the array (assume the array is read only).
• You must use only constant, O(1) extra space.
• Your runtime complexity should be less than O(n2).
• There is only one duplicate number in the array, but it could be repeated more than once.
  

如果没有限制修改数组，有没有什么其他的算法？

允许修改原数组的话，就用pigeonhole principle直接sort。
O(n) time, O(1) space

1. int findDuplicate(vector<int>& nums) {
   
2. 
   
3.         for(int i=0; i<nums.size(); i++) {
   
4.             
   
5.             int val = nums[i];
   
6.             if(i!=val){
   
7.                
   
8.                 if(nums[val]==val)
   
9.                     return val;
   
10.                 swap(nums[val], nums[i]);
    
11.                 i--;
    
12.             }
    
13.             
    
14.         }
    
15.         
    
16.         return -1;
    
17.     }

复制代码

111180611 发表于 2016-6-1 02:01
为什么low从1开始？

从0开始应该也是对的。。因为不存在length小于2的情况。。
我的java代码这么写的，能过：
public int findDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        while (start<end){
            int mid = start+(end-start)/2;
            int count = 0;
            for (int num : nums){
                if (num<=mid) count++;
            }
            if (count>mid) end = mid;
            else start = mid+1;
        }
        return start;
    }

int findDuplicate(vector<int>& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {
      int mid = low + (high - low) / 2;
      int c = 0;
      for(int i = 0; i < nums.size(); i++) {
         if(nums <= mid) c++;
      }
      if(c <= mid)
         low = mid + 1;
      else
         high = mid;
   }
   return nums[low];
}

hashmap, first sort then binary search

JimmyZhuang 发表于 2016-5-31 08:36
int findDuplicate(vector& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {

you need to sort first

blackrose 发表于 2016-5-31 10:55
you need to sort first

No, I don't need to sort. Take a look at my low and high, they are not indexes.

JimmyZhuang 发表于 2016-5-31 08:36
int findDuplicate(vector& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {

二楼最后返回的结果应该是low，不是nums[low]

请问一下，这个不是全都取异或看剩下来的数就行了吗？

vae371 发表于 2016-5-31 22:37
请问一下，这个不是全都取异或看剩下来的数就行了吗？

那是另外一道题。。这个重复可以重复很多次的。。

答案那个O(n)的做法是把这个看成linkedlist cycle...好难想。。还是binary search那个，判断这个数是否小于当前的mid，比较好想。。