困惑：找到一个数组中最常见的入门 [英] Puzzle: Find the most common entry in an array

问题描述

正在给定长度的32位无符号整数数组高达2 ³² ，与属性，超过阵列中的条目的一半是等于N，对于某些32位无符号整数N.求n看着阵列中的每个号码只有一次，使用的存储器至多2 kB的

You are given a 32-bit unsigned integer array with length up to 2³², with the property that more than half of the entries in the array are equal to N, for some 32-bit unsigned integer N. Find N looking at each number in the array only once and using at most 2 kB of memory.

您的解决方案必须是确定的，并保证求n。

Your solution must be deterministic, and guaranteed to find N.

推荐答案

请有一个整数的每一位，并适当增加该集合的阵列中的每个整数。

Keep one integer for each bit, and increment this collection appropriately for each integer in the array.

目前结束时，一些位将具有计数比数组的长度的一半更高 - 那些位决定N.当然，计数将比次数N发生的数量较高，但也不物。重要的是，任何一点这不是氮的部分不能的发生有一半以上的时间（因为N有一半以上的项目）以及任何位这是N 部分必须的一半以上的时间发生更多（因为它会出现每次时间N发生，以及任何额外的）。

At the end, some of the bits will have a count higher than half the length of the array - those bits determine N. Of course, the count will be higher than the number of times N occurred, but that doesn't matter. The important thing is that any bit which isn't part of N cannot occur more than half the times (because N has over half the entries) and any bit which is part of N must occur more than half the times (because it will occur every time N occurs, and any extras).

（没有code的时刻 - 。即将失去网络访问希望上面是再清楚不过虽然）

(No code at the moment - about to lose net access. Hopefully the above is clear enough though.)

这篇关于困惑：找到一个数组中最常见的入门的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！