在数组中查找最常见的条目 [英] Find the most common entry in an array

问题描述

为您提供了一个长度不超过2 ³² 的32位无符号整数数组，其特性是对于某些32位，该数组中超过一半的条目等于N无符号整数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 的任何位都必须发生的次数超过一半(因为每次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).

(目前尚无代码-即将失去网络访问权限.希望以上内容足够清楚.)

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

这篇关于在数组中查找最常见的条目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！