【数组】-找出数组中第一个重复的数字

写在前面

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

---

---

一、场景描述

  在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。 请找出数组中第一个重复的数字，没有重复的数字，则返回 -1。示例：{2,3,1,0,2,5,3}，返回 2

  判断是否重复，我们可以借助Map进行过滤。

---

二、具体步骤

1.环境说明

2.代码

以下为Java版本实现：

public class ArrayDuplicateTest {

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

    /**
     * 思路：
     * 定义Map：key为数组中的元素，value为元素在数组中的索引
     *
     * 循环数组
     * 判断map中是否存在：
     * 	存在则返回
     * 	不存在，则放入map中
     *
     * 循环结束，说明没有重复的，直接返回-1
     *
     * 最后考虑数组边界
     *
     * @param array
     * @return
     */
    private static int findDuplicate(int[] array) {
        if (array.length <= 1) {
            return -1;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (map.containsKey(array[i])) {
                return array[i];
            } else {
                map.put(array[i], i);
            }
        }
        return -1;
    }
}

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

---

写在后面

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