Java如何查找数组中重复的数

x33g5p2x  于2021-03-13 发布在 Java  
字(1.8k)|赞(0)|评价(0)|浏览(298)

给出一个数组 nums 包含 n + 1 个整数,每个整数是从 1 到 n (包括边界),保证至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

注意事项
1.不能修改数组(假设数组只能读)
2.只能用额外的O(1)的空间
3.时间复杂度小于O(n^2)
4.数组中只有一个重复的数,但可能重复超过一次

样例

给出 nums = [5,5,4,3,2,1],返回 5.
给出 nums = [5,4,4,3,2,1],返回 4.

分析

输入:int[]
输出:`int

数组为null`null`   
为空数组`int []{}`
[5,5,4,3,2,1]
[5,4,4,3,2,1]
[5,3,3,1,1,1]

```

### 思路

先考虑可以修改数组的查找方法。
1.排序后查找重复的数,这样的复杂度为O(NlogN)和O(1)
2.使用一个hash表,有碰撞时就可以找到重复的值 复杂度为O(NlogN)和O(N)

**可修改数组**
题目中描述整数从1到n,如果不在此范围内的任意数,也可以使用上面的方法,而有了范围的限定,可以考虑使用其他方法,查看是否可降低至O(N)
nums中包含n+1个整数,从1-n,如果排序后,数组中是1,2,3....n,可以看到数组的值为index+1,例如,nums = [5,5,4,3,2,1],排序后为[1,2,3,4,5,5] 当nums[i]!=i时,说明有重复数据

```
public int findDuplicate(int[] nums) {
    if(nums == null||nums.length == 0) {
        return -1;
    }
    // 修改数组的方法 O(n)
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] - 1 != i) {
            int b = nums[i] - 1; // i所在的index
            int e = nums[b]; // i所在的index的值
            if (e == nums[i]) {
                return e;
            } else { // 不一样 swap i&b
                int tmp = nums[b];
                nums[b] = nums[i];
                nums[i] = tmp;
            }
        }
    }
    return 0;
}

```
**不可修改数组**
如果限定为不能修改数组,那么就不能排序了,哈希表还是可以使用的,复杂度为O(N)和O(N);  
还可以使用计数法,从i=0开始,统计1-n中nums[i]的个数,复杂度为O(N^2)和O(1);
可以考虑O(NlogN)和O(1),当时没有想出来,但是范围在1-n,可以考虑二分法,首先,数组n+1个元素,范围为1-n,因此肯定存在重复的数。可以先而分为[1,(n-1)/2+1]和[(n-1)/2+2,n],遍历数组,如果在范围内的数量大于范围的数量,如:[1,9]分为[1,5]和[6,9],查找数组中[1,5]的数量,如果没有重复的,则数量为5,如果大于5说明[1,5]中有重复的值,然后在拆分为[1,3]和[4,5],再进行查找,复杂度为O(NlogN)和O(1);

```
public int findDuplicate(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int min = 1;
    int max = nums.length - 1;
    while (true) {
        int mid = (max - min) / 2;
        mid = min + mid;
        int minSize = getSize(nums, min, mid);
        if (minSize > (mid - min + 1)) {
            if (mid == min) {
                return min;
            } else {
                max = mid;
                continue;
            }

        }
        int maxSize = getSize(nums, mid + 1, max);
        if (maxSize > (max - mid)) {
            if (mid + 1 == max) {
                return max;
            } else {
                min = mid + 1;
                continue;
            }
        }

    }
}

public int getSize(int a[], int min, int max) {
    int ret = 0;
    int count = max - min + 1;
    for (int i = 0; i < a.length; i++) {
        if (a[i] >= min && a[i] <= max) {
            ret++;
            if (ret > count) {
                return ret;
            }
        }
    }
    return ret;
}

```

相关文章

热门文章

更多