【数组】-数组里的所有数字都在 0 到 n-1范围内，判断该数组中是否有重复的数

写在前面

  最近想复习一下数据结构与算法相关的内容，找一些题来做一做。如有更好思路，欢迎指正。

---

---

一、场景描述

  在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内，判断该数组中是否有重复的数。
示例： [2,3,1,0,2,5,3] 返回 true

  可以使用Map作为过滤，思路也很简单。循环数组中的元素，不存在就加入map，存在就返回 true，循环结束，没找到直接返回 false。可参考【数组】-找出数组中第一个重复的数字

  也有一种类似排序的方式可以实现，时间复杂度O(n)，空间复杂度O(1)。由于题目的条件约束是数组中的元素值都在 0 - n-1之间，那么我们就可以给数组中每个元素都放到对应数组的索引位置上（比如当前元素的值为2，我们就把2放到 array[2] 的位置上），如果在索引位置上（比如：array[2]）找到了同样的元素，就说明有重复值，否则，交换，继续循环。直至循环结束，说明没有找到重复值，具体参见代码中的思路。不过这种方式，也仅限于算法。日常编码，我们大概率用不到这种方式，因为多数情况下我们不会去改变原数组的数据或者位置。

---

二、具体步骤

1.环境说明

2.代码

以下为Java版本实现：

public class ArrayIsDuplicateTest {

    public static void main(String[] args) {
//        int[] array = {2, 3, 1, 0, 2, 5, 3};
        int[] array = {0, 1};
        System.out.println(isDuplicate(array));
    }

    /**
     * 思路：
     *
     * 条件约束：
     * 1.n个元素
     * 2.数组中所有数组都是 0 - n-1 之间
     *
     * 这2个条件意味着：
     * 如果数组不重复（0 - n-1的数字必定都在数组中）；
     * 重复，（0 - n-1的数字至少有一个在数组中重复）
     *
     * 循环数组
     *    while 判断 当前元素和索引下表值是否相同
     *      不相同，判断当前元素的值 array[i] 是否和当前元素值作为索引在数组位置上的值 array[array[i]] 是否相等
     *          相等，直接返回 true
     *          否则，就把 array[i] 和 array[array[i]] 的值交换（相当于给 array[i] 找到了正确的位置），继续while循环
     *    说明：while循环的结束条件：要么是找到相同的元素了，直接返回；要么是交换后当前元素的位置也正确了，跳出while循环，继续数组for的下一轮循环
     *
     * 数组循环结束（每个元素都找到了正确的位置），即没有找到重复的数，返回false
     *
     * @param array
     * @return
     */
    private static boolean isDuplicate(int[] array) {
        for (int i = 0; i < array.length; i++) {
            while (array[i] != i) {
                if (array[i] == array[array[i]]) {
                    return true;
                }
                // 交换
                int temp = array[array[i]];
                array[array[i]] = array[i];
                array[i] = temp;
            }
        }

        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

---

写在后面

  如果本文内容对您有价值或者有启发的话，欢迎点赞、关注、评论和转发。您的反馈和陪伴将促进我们共同进步和成长。