力扣剑指 Offer 56 - I. 数组中数字出现的次数

153 阅读 0 评论 101 点赞

我是靠谱客的博主坚强汉堡，这篇文章主要介绍力扣剑指 Offer 56 - I. 数组中数字出现的次数，现在分享给大家，希望可以做个参考。

题目来源：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

大致题意：
给定一个一维数组，其中只有两个数出现了一次，其余的数都出现了两次，找出出现一次的两个数

思路

对于出现两次的数，可以使用位运算中的亦或运算进行去除，即

a ^ b ^ a ^ b = 0

那么遍历数组，对整个数组的元素进行异或操作，最终得到的结果就是出现一次那两个数异或的结果

于是，接下来的任务就是根据异或的结果分离出这两个数

已知，异或运算只有对应位的值不相同才为 1，那么可以在异或结果找出某个 1 出现的位置，然后将其取出

可以知道，对于该位置，待求的两个数有一个在该位为 1，有一个在该位为 0

那么，可以通过再次遍历数组，进行分组异或操作，即根据在取出位置是否为 1 进行分组异或，最终两组结果的异或值即为所求两个数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
	public int[] singleNumbers(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum ^= num;
        }
        // 找出异或结果中最低位的 1
        int bit = 1;
        while ((sum & 1) == 0) {
            sum >>= 1;
            bit <<= 1;
        }
        int[] ans = new int[2];
        for (int num : nums) {
        	// 分组异或
            if ((num & bit) == 0) {
                ans[0] ^= num;
            } else {
                ans[1] ^= num;
            } 
        }
        return ans;
    }