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

Question

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

q：确定数组中最显示的元素。我能够解决它，但很好奇看别人的解决方案。因此，我遇到了使用位操作的解决方案。

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]，第一个循环后，位[0]将包含4，位[1] = 2，bit [3] = 3和所有其他位将为0。

根据我的理解，第二个循环将导致位置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所指出的，您需要反向频率计数器中的索引以及结果计算以使您的简化工作。