首页 > 代码库 > Redis 存储结构设计

Redis 存储结构设计

其他出现两次,只有一个出现一次的那道题我就不更了,直接抑或,最后的结果就是那个数。为什么可以这样做呢?因为一个32位int,如果所有数都出现了两次,那么为1的那些位统计的个数一定是2的倍数,抑或之后全变成0。一个数出现了一次,它为1的那些位上,1的个数必定是奇数,抑或之后一定还是1。

我之前知道出现两次这个题的解法,但是理解的不够深,以为抑或是关键,其实不是,出现了偶数次才是关键。理解了这点,推广到出现3次上,如果所有的出现了三次,那么为1的那些位1的个数一定是三的倍数,那如果有一个数出现了一次呢?没错,它为1的那些以三余模之后,肯定是1。换言之,出现几次都可以用同样的思想解,只不过如果这个重复次数不是偶数,就不能用抑或简单的解决,而是一位一位的用一个量来保存位运算的结果,一看代码就明白了。

还有一个有趣的问题,是剑指offer上的,如果一个数组中只有两个数出现了一次,其他都出现了两次,怎么快速找出这两个数呢?这次的关键是抑或操作。想想把数组抑或之后得到的结果是什么呢?出现两次的数都被自己抑或成了0,对,相当于这两个出现了一次的数的抑或,他们抑或的结果是什么呢?不同的位被置1,相同的位被置0。两个数不同,所以至少有一位被置1了。我们可以根据这一位来分类,这一位为0的归为一类,为1的归为一类,这两类分别抑或,得到的就是要求的那两个数了。

最后还是贴上三次一个的代码:

class Solution {
public:
    int singleNumber(int A[], int n) {
        int res=0;
        for(int i=0;i<32;i++){
            int count = 0;
            for(int j=0;j<n;j++){
                count += (A[j]>>i)&1;
            }
            res |= ((count%3)<<i);
        }
        return res;
    }
};