Divide

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/15/]

给定一个长度为 n+1的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

1
2
3
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？

算法描述

举例理解，相当于有n个坑，n+1个萝卜，总会多出来一个萝卜；采用分治法，空间复杂度为O(1),统计在一个区间数据的个数，如果个数大于区间大小则必定存在重复值；一直分治下去即可；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
       int l = 1,r = nums.size()-1;
       while(l<r){
           int mid = r+l >> 1;
           int sum =0;
           for(auto val : nums)sum+=val>=l&&val<=mid;
           if(sum>mid-l+1)r = mid;
           else l = mid +1;
       }
       return r;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int duplicateInArray(int[] nums) {
        int l=1,r=nums.length-1;
        while(r>l){
            int mid = r+l>>1;
            int sum=0;
            for(int val:nums)
                if(val>=l&&val<=mid)sum++;
            if(sum>mid-l+1)r=mid;
            else l=mid+1;
        }
        return r;
    }
}