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

ゝ一世哀愁。 2022-04-24 13:52 245阅读 0赞

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

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。从数组中找出任意一个重复的数字，但不能修改输入的数组。如\{2,3,5,4,3,2,6,7\}得到2或者3.

解法1：

1）创建一个长度为n+1的辅助数组，然后逐一把原数组的每个数字复制到辅助数组

2）如果原数组中被复制的数字是m，就把它复制到下标为m的位置，这样就能发现重复的数字

由于需要创建一个数组，该方案需要O(n)的辅助空间

解法2：运用二分查找算法的概念（最优）

1）把1~n的数字从中间的数字m分为两部分，前面一半为1~m，后面一半为m+1~n

2）如果1~m这部分的数字对应数组里的值超过m个，这个区间就包含有重复的数字，否则就是另外一个区间包含重复的数字。就算两个区间都有重复的也只要再对某一个区间进行二分，因为题目要求只要找到任意一个重复的数字

3）继续把重复数字的区间进行二分，直到找到一个重复的数字

int getDuplication(int[] numbers,int length){
    
            int start = 1;
            int end = length - 1;
            while (end >= start){
                /**
                 * int mid = (start+end)/2可能会溢出，用>>是遇到负奇数的时候求上下界统一
                 * -5/2=-2   5/2=2   上下界求法不统一
                 * -5>>1=-3  5>>1=2  统一
                 */
                int mid = start + (end - start)>>1;
                int count = countRange(numbers,length,start,mid);
                if (end == start){
                    if (count>1){
                      return start;
                    }
                    break;
                }
    
                /*if (count>mid){
                    end = mid - 1;
                }else {
                    start = mid + 1;
                }*/
                if (count>(mid-start+1)){
                    end = mid;
                }else {
                    start = mid + 1;
                }
            }
            return -1;
        }
    
        int countRange(int[] numbers,int length,int start,int end){
            int count = 0;
            for (int i = 0; i < length; i++) {
                if (numbers[i]>=start&&numbers[i]<=end){
                  ++count;
                }
            }
            return count;
        }