判断集合中只出现1次的元素

第一次体会到位运算的魅力是遇见Leetcode上“[136] 只出现一次的数字”:

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

如果当成一个模拟题来做这题就失去了存在的意义,但有一种方法初看来会有些让人一头雾水:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(int i = 0;i < nums.length(); i++){
            result = result ^ nums[i];
        }
        return result;
    }
};

“^”符号在位运算中表示异或,处理二进制中两个数的异或时,相同为0,相异为1。相同的十进制数取异或后得到0,那么只出现一次的数就是最后的结果。

拓展思考

数组A中,除了某一个数字x之外,其他数字都出现了三次,而x出现了一次。请给出最快的方法找到x。

出现三次的元素就无法使用异或的方法了,不妨看看出现三次的十进制整数的二进制有什么特点:

  • 1:0001
  • 5:0101
  • 1:0001
  • 5:0101
  • 1:0001
  • 5:0101

很容易注意到,如果数组中没有出现一次的元素,数组中所有元素在同一位上“1”的个数必然是3的倍数,如第0位有6个“1”,第2位有3个“1”,新引入的出现一次的元素必然会大批这个平衡,故统计数组所有元素同一位“1”的个数即可判断出仅出现一次的元素。

#include <cstring>

int FindNumber(int a[], int n) {
    int bits[32];
    int i, j;
    memset(bits, 0, 32 * sizeof(int));
    for (i = 0; i < n; i++)
        for (j = 0; j < 32; j++)
            bits[j] += ((a[i] >> j) & 1);  // 计算每个数的二进制位数的个数
            // 取int型变量a的第k位 (k=0,1,2……sizeof(int)),即a>>k&1
    // 如果某位上的结果不能被整除,则肯定目标数字在这一位上为
    int result = 0;
    for (j = 0; j < 32; j++)
        if (bits[j] % 3 != 0)
            result += (1 << j);
    return result;
}

在今后遇见的所有元素出现N(N>=3)次的数组中找只出现一次的问题均可采用类似方法。

实际上,位运算不仅性能表现更优,在处理以下问题时还能使代码更加优雅。

判断奇偶

  • a&1 = 0 偶数
  • a&1 = 1 奇数
    由于十进制数“1”的二进制“0000....0001”只有末位是1,与偶数按位与后为0,与奇数按位与后为1。

对整形变量的第k位进行操作

  • 取int型变量a的第k位 (k=0,1,2……sizeof(int)),即a>>k&1
  • 将int型变量a的第k位清0,即a=a&~(1<<k)
  • 将int型变量a的第k位置1,即a=a|(1<<k)

整数的平均

对于两个整数x,y,如果用 (x+y)/2 求平均值,会产生溢出,因为 x+y 可能会大于INT_MAX,但是我们知道它们的平均值是肯定不会溢出的,我们用如下算法:

int average(int x, int y)   //返回X,Y 的平均值
{   
     return (x&y)+((x^y)>>1);
}

判断一个整数是不是2的幂

对于一个数 x >= 0,判断他是不是2的幂。

boolean power2(int x)
{
    return ((x&(x-1))==0)&&(x!=0);
}
Last modification:July 21st, 2019 at 09:17 am
If you think my article is useful to you, please feel free to appreciate