数据结构【数组】（三）：查找数组中第一个不重复的数

待我称王封你为后i 2022-03-06 05:28 174阅读 0赞

## 1、问题描述 ##

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个重复的数字。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

数组 : -1 2 -1 3 2
    第一个不重复元素 : 3
    
    
    数组 : 9 4 9 6 7 4
    第一个不重复元素 : 6

## 2、代码实现 ##

### 解题1：双层循环 ###

一个简单的解决方案是使用两个循环。外部循环逐个遍历元素，内部循环检查元素是否存在多次或不存在。

private static int firstNonRepeating(int[] arr, int n) {
            //外层循环逐个遍历元素
            for (int i = 0; i < n; i++) {
                int j;
                //内层循环判断元素是否存在
                for (j = 0; j < n; j++) {
                    if (i != j && arr[i] == arr[j]) {
                        break;
                    }
                }
                if (j == n) {
                    return arr[i];
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {
    
            int[] arr = {9, 4, 9, 6, 7, 4};
            int n = arr.length;
    
            System.out.print(firstNonRepeating(arr, n));
        }

### 解题1：使用散列表 ###

1）遍历数组元素，并插入到哈希表中记录每个元素出现的次数

2）再次遍历哈希表，值为0的便是不重复的数字

/**
         * @param arr 数组
         * @param n   数组长度
         */
        public static int findFirstNotRepeat(int[] arr, int n) {
            //对每个元素进行计数
            Map<Integer, Integer> map = new LinkedHashMap<>();
            //遍历数组
            for (int i = 0; i < n; i++) {
                //如果map中存在该元素，则对应的数量加1
                if (map.containsKey(arr[i])) {
                    int value = map.get(arr[i]);
                    map.put(arr[i], value + 1);
                } else {
                    //每个元素初始次数为0
                    map.put(arr[i], 0);
                }
            }
            //值为0的便是不重复的数
            for (Integer key : map.keySet()) {
                if (map.get(key).equals(0)) {
                    return key;
                }
            }
            return -1;
        }
    
    
        public static void main(String[] args) {
    
            int[] arr = {9, 4, 9, 6, 7, 4};
            int n = arr.length;
    
            System.out.print(findFirstNotRepeat(arr, n));
        }