剑指offer—不改变数组找到重复的数 解答

剑指offer—不改变数组找到重复的数

题目

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3

说明:

不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字,但它可能不止重复出现一次。

思路

  • 二分法

长度为n+1的数组全部数都在1-n,所以至少有一个数出现过。

给出左边界和右边界,中点为一半,遍历数组,小于中点的数放在左边(实际不要辅助空间放,而是使用count计数),如果count值大于中点值,则说明重复的数在左边,反之在右边。根据情况缩小边界,继续循环,知道左边界不小于右边界,就得到了重复的数就是边界处的值。

代码

class Solution {
    public int findDuplicate(int[] nums) {
        int l = 0,r = nums.length - 1;
        while(r>l){
            int mid = l + r >> 1;//右移1代表为原来一半
            int count = 0;
            //小于中点的数放在左边,如果左边的个数大于中点,重复数在左边
            for(int i:nums){
                if(i<=mid){
                    count++;
                }
            }
            if(count>mid){
                r = mid;//在左边
            }else{
                l = mid + 1;//在右边
            }
        }
        return l;
    }
}