算法基础算法

异或的性质，数字出现次数问题

字数统计: 1.2k字   |   阅读时长: 5分
, , ,

摘要: 利用异或的性质，解决数组中数字出现次数的问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

异或的性质

  • 交换律: $p \oplus q = q \oplus p$
  • 结合律: $p \oplus (q \oplus r) = (q \oplus p) \oplus r$
  • 恒等律: $p \oplus 0 = p$
  • 归零律: $p \oplus p = 0$

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：
输入：nums = [2,2,1]
输出：1

示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：
输入：nums = [1]
输出：1

提示：

1
2
3
1 <= nums.length <= 3e4
-3e4 <= nums[i] <= 3e4
除了某个元素只出现一次以外，其余每个元素均出现两次。

算法：异或

全部元素进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 0，不同结果为 1。

那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int xor_result = 0;
        for(int num : nums)
        {
            xor_result ^= num;
        }
        return xor_result;
    }
};

260. 只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

提示：

1
2
3
2 <= nums.length <= 3e4
-2^31 <= nums[i] <= 2^31 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

示例 1：
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：
输入：nums = [-1,0]
输出：[-1,0]

示例 3：
输入：nums = [0,1]
输出：[1,0]

算法：分组异或

记两个只出现 1 次的元素为 a, b。将数组分为 2 部分 A 和 B。会出现两种情况。

  1. a, b 分别出现在两个不同的部分中。
  2. a, b 出现在同一个部分中。

如果是第 1 种情况，即分成的两部分 A，B 各自含有 a, b 中的 1 个。此时将两部分分别对所有元素求异或，两部分的最终异或值就对应所要求的两个数。

此时问题就是如何将原数组分成各自含有 a, b 其中之一的两个部分 A 和 B。

记所有元素的异或为 x。将 x 写成二进制形式 $x = ..x_{k}..x_{1}x_{0}$。

对某个位 i: 若 $x_{i} = 0$, 则 a, b 在位 i 是不同的，因此如果以第 i 位为标准，第 i 位是 1，则分在第一组，第 i 位是 0，则分在第 2 组。此时，两组就各自含有 a, b 之一了。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x = 0;
        for(int num: nums) x ^= num;
        int k = 0;
        while(x)
        {
            if(x & 1)
                break;
            ++k;
            x >>= 1;
        }
        int x1 = 0, x2 = 0;
        for(int num: nums)
        {
            if((num >> k) & 1)
                x1 ^= num;
            else
                x2 ^= num;
        }
        return {x1, x2};
    }
};

137. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

提示：

1
2
3
1 <= nums.length <= 3e4
-2^31 <= nums[i] <= 2^31 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

示例 1：
输入：nums = [2,2,3,2]
输出：3

示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99

算法：统计各个位

按各个位来看，一共 32 位(0~31)。

记目标数为 x。

对于位 i，该位为 1 的个数为 cnt，有两种情况：

  • cnt 模 3 余 0 : 该位不在目标数里(xi = 1)。
  • cnt 模 3 余 1 : 该位在目标数里(xi = 0)。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(int i = 0; i <= 31; ++i)
        {
            int count = 0;
            for(int num : nums)
                if(num >> i & 1)
                    ++count;
            if(count % 3 == 1) result += (1 << i);
        }
        return result;
    }
};
Share