algorithm - 查找数组中最常见的条目

Question

给你一个长度最大为 2³² 的 32 位无符号整数数组，其属性是数组中超过一半的条目等于 N，对于某些 32 位无符号整数 N。查找 N，只查看数组中的每个数字一次，并且最多使用 2 kB 内存。

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

Answer 1

为每一位保留一个整数，并为数组中的每个整数适本地递增此集合。

最后，一些位的计数会大于数组长度的一半——这些位决定了 N。当然，计数会大于 N 出现的次数，但事实并非如此事情。重要的是任何不属于 N 的位不能出现超过一半的次数(因为 N 有超过一半的条目)并且属于 N 的任何位必须 出现的次数超过一半(因为每次出现 N 和任何额外的时候都会出现)。

(目前没有代码 - 即将失去网络访问权限。希望上面的内容足够清楚。)