找到数组中最常见的条目

您将获得一个32位无符号整数数组,其长度最大为2 ³²,其中包含数组中一半以上条目的属性等于N,对于某些32位无符号整数N.查找N查看每个数字在数组中只使用一次并使用最多2 kB的内存.

您的解决方案必须是确定性的,并保证找到N.

为每个位保留一个整数,并为数组中的每个整数适当增加此集合.

最后,一些位的计数高于数组长度的一半 - 这些位确定N.当然,计数将高于N出现的次数,但这并不重要.重要的是,任何不属于N的位都不能超过一半的次数(因为N超过一半的条目)并且任何属于N的位必须出现超过一半的次数(因为它会发生)每次N发生,以及任何额外的).

(目前没有代码 - 即将失去网络访问权限.希望上述内容已经足够清晰了.)

Boyer和Moore的"线性时间多数投票算法" - 沿阵列向下,保持你当前的猜测答案.

你只需要两个变量就可以做到这一点.

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}