【位运算技巧】异或运算符(1)找出落单的数

【位运算技巧】异或运算符(1)找出落单的数

前言

位运算 异或(^)蛮有意思的,分享一下。

一、题目

一个数组里除了某一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

提示:异或( ^ )可以去除两个重复的值。

二、题解

1.奇巧淫技

直接使用 异或 去重即可。

    public static int solution(int[] arr) {
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            num ^= arr[i];
        }
        return num;
    }

测试数据

    public static void main(String[] args) {
        // 测试数据
        int[] arr = {1, 1, 3, 3, 5, 5, 99};

        // 题解
        System.out.println(solution(arr));
    }

2.其他解法

排序遍历

排序后,暴力破解。时间复杂度O(nlong(n))

    public static int solution2(int[] arr) {
        Arrays.sort(arr);
        int len = arr.length;
        for (int i = 0; i < len - 1; i += 2) {
            if (arr[i] != arr[i + 1]) {
                return arr[i];
            }
        }
        // 最后一个
        return arr[len - 1];
    }
哈希表

哈希表。时间复杂度O(n)

    public static int solution3(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])) { // 不包含
                map.put(arr[i], 1);
            } else {
                map.put(arr[i], 2);
            }
        }

        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            Integer value = entry.getValue();
            if (value == 1) {
                return entry.getKey();
            }
        }
        throw new IllegalArgumentException("数组中不存在落单的数!");
    }