数组中多数元素的位操作解决方案

Question

资料来源:https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation/2

问:确定数组中出现最多的元素.我能够解决它,但很想看别人的解决方案.所以我遇到了使用位操作的解决方案.

public int majorityElement(int[] nums) {
    int[] bit = new int[32];
    for (int num: nums)
        for (int i=0; i<32; i++) 
            if ((num>>(31-i) & 1) == 1)
                bit[i]++;
    int ret=0;
    for (int i=0; i<32; i++) {
        bit[i]=bit[i]>nums.length/2?1:0;
        ret += bit[i]*(1<<(31-i));
    }
    return ret;
}

当我更换线路

ret += bit[i]*(1<<(31-i)); 

同

ret += bit[i]*(1<<i);

我最终得到一个负数.

考虑输入数组 - [2,5,5,5,3],在第一个for循环之后,bit [0]将包含4,bit [1] = 2,bit [3] = 3,所有其他位将是0.

根据我的理解,第二个for循环将导致其位位置31和29设置为1的数字(与5不同).在我的理解中,我显然遗漏了一些东西.

有人可以解释这段代码是如何工作的？谢谢.

Answer 1

该算法首先确定输入数组中每个比特的频率.如果输入中存在多数的数字(即它占输入的一半以上),则其所有设置位的频率将占多数,并且其所有未设置位的频率将在少数民族.

通过将所有多数位掩码在一起,可以从频率表重新创​​建多数.这取决于多数人.如果没有保证成为多数,则需要第二次通过以检查结果.

public static int majorityElement4(int[] nums) {
    // Bit frequency table 
    int[] bit = new int[32];

    // Work out bit frequency
    for (int num : nums)
        for (int i = 0; i < 32; i++)   // for each bit
            if ((num & 1 << i) != 0)   // is bit i set?
                bit[i]++;              // increment frequency

    // Recreate the majority number 
    int ret = 0;
    for (int i = 0; i < 32; i++)       // for each bit   
        if (bit[i] > nums.length / 2)  // is bit i in the majority?
            ret |= 1 << i;             // mask bit i into the result
    return ret;
}

如@Louis所述,您需要反转频率计数器中的索引以及结果计算,以使您的简化工作.