数据结构【数组】（四）：查找数组中不重复的数

ゞ浴缸里的玫瑰 2022-03-06 05:28 305阅读 0赞

## 1、问题描述 ##

在一个整型数组中，有些数字是重复的，有些是不重复的，请找出不重复的元素。

举例：

1、有且仅有一个数字不重复情况
    数组：2 4 3 6 3 2 5 6 5
    输出：4
    
    2、多个数字不重复情况
    数组：2 4 3 6 3 2 5 5
    输出：4，6

## 2、代码实现 ##

### 2.1、不重复数字有且仅有一个情况 ###

该种情况可以使用位运算，一个数异或它本身等于0

public static void main(String[] args) {
            int[] arr = {2, 4, 3, 6, 3, 2, 5, 6, 5};
            System.out.println(findNotRepeat(arr));
    
        }
    
        public static int findNotRepeat(int[] arr) {
            int len = arr.length;
            int res = -1;
            if (len > 1) {
                res = arr[0];
                for (int i = 1; i < len; i++) {
                    res = res ^ arr[i];
                }
            }
            return res;
        }

### 2.2、不重复数字多于1个情况 ###

数组中不重复的数大于一个，则可以遍历一次数组，使用一个map记录数与数出现的次数；接着，再遍历一次map，找出次数为1的数，即为我们要找的数

/**
         * @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], 1);
                }
            }
            //值为0的便是不重复的数
            for (Integer key : map.keySet()) {
                if (map.get(key).equals(1)) {
                    return key;
                }
            }
            return -1;
        }