剑指offer3.数组中重复的数字

剑指offer3.数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

题解

这道题目解法还是很多的,可以对数组进行排序,还可以将数组中的元素全部放到一个HashMap中,还可以创建一个辅助数组,但是这里介绍一下“有意义”的方法

因为这道题数组中的数字是比较特殊,分布范围全部在0~n-1之间,如果没有重复数组,那么最终每个数组中元素和索引都是相等的:arr[i] == i,如果出现不相等,我们进行交换,使其放到子集应该对应的索引处,如果如果应该对应的索引之处已经对应好,那么出现重复,光说比较抽象,直接上代码:

package java2;

public class Solution {
    public int duplicate(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == i) continue;
            while(arr[i] != i){
                if(arr[arr[i]] == arr[i])   return arr[i];
                swap(arr,i,arr[i]);
            }
        }
        return -1;
    }
    //交换方法使用到了上一篇博客中的装逼方法
    private void swap(int[] arr,int i,int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {2,3,1,0,2,5};
        System.out.println(solution.duplicate(arr));
    }
}

后面有一个扩展:

在一个长度为n+1的数组里的所有数字在1~n的范围内,所以数组至少有一个数字是重复的,请找出任意一个

这道题和上面那个只有一点点不一样,也是可以通过改变数组交换的方法解决,那么我们能否不改变数组实现呢?

(当然这里就不讨论使用额外空间的方法了)

这里可以用到二分查找的思想,刚刚意识到这种方法的重要性,在这道题目上还是没有主动用到,看来今后只要一做题就要看一下二分查找是否使用

package java2;

public class Solution {
    public int duplicate(int[] arr){
        int left = 1;
        int right = arr.length - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            int count = countRange(arr,left,mid);
            if(left == right){
                if(count > 1)   return left;
                else break;
            }
            if(count > (mid - left + 1))
                right = mid;
            else
                left = mid + 1;
        }
        return -1;
    }
    private int countRange(int[] arr,int left,int right){
        if(arr == null || left < 0 || right < 0 || left > right)    return -1;
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] >= left && arr[i] <= right)
                count++;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {2,3,5,4,3,2,6,7};
        int duplicate = solution.duplicate(arr);
        System.out.println(duplicate);
    }
}

这种方法根据这个数组的特殊性,如果在1~n的区间中出现了n+1个数字,那么一定有重复,我们使用这般查找的方法,每次可以砍掉一半的空间,但是每一次都需要遍历数组,所以实践复杂度为O(nlog(n))

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/剑指offer3数组中重复的数字md