找到数组中最常见的条目

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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;
}

将第一个数字设为可疑号码,然后继续循环浏览列表.如果数字匹配,将怀疑强度提高一个; 如果不匹配,请将怀疑强度降低一个.如果怀疑强度达到0,则当前数字成为可疑数字.这不能找到最常见的数字,只能找到超过该组50%的数字.如果suspicionStrength大于列表长度的一半,则拒绝添加支票的冲动- 它总是会导致更多的总比较.

PS我没有测试过这段代码 - 使用它自担风险.