The question is:
问题是:
Describe an algorithm that find in O(n) time if there is in an array of n numbers,a number that appears more than n/8 times.
描述一个在O(n)时间内发现的算法，如果数组中有n个数字，这个数字会出现超过n/8次。
Now I have the answer which is:
现在我得到的答案是:
We'll do Select for the numbers in places: n/9,2*n/9,3*n/9,...,8*n/9 , and than check if one of those 8 candidates appears at least n/8 times.
我们将在一些地方选择数字:n/9,2*n/9,3*n/9，…，8*n/9，而不是检查这8个候选人中是否有一个出现至少n/8次。
But I don't understand why would this algorithm work.
但是我不明白为什么这个算法会起作用。
For example,consider the following array: [3,3,1,3,2,3,4,3,5,3,6,3,7,3,8,3,9,3].
例如，考虑以下数组:[3、3、1、3、2、3、4、3、5、3、6、3、7、3、8、3、9、3]。
So here n=18, and if for this algorithm the candidates would be 1,2,4,5,6,7,8,9 and when we'll check if these numbers appear at least n/8 times the answer will be no,but actually for 3 the answer would be yes.
这里n=18，如果这个算法的候选项是1 2 4 5 6 7 8 9，当我们检查这些数字是否至少出现n/8时答案是否定的，但实际上答案是肯定的。
So I don't understand why is this algorithm correct...
我不明白为什么这个算法是正确的…
1 个解决方案
#1
0
The key insight here is that Select, especially when capitalised, has a special meaning: it references the problem of finding the kth largest entry in an unsorted array. Perhaps somewhat surprisingly a priori, this can be done in linear time, for example using a median-of-5 pivoting strategy in combination with the QuickSelect algorithm. So if you Select-with-an-uppercase-S the n/9, 2n/9, ... entries (cost: 9*linear - which is linear), you definitely find any entries that occur n/8 times. Then iterate through your array again to count the number of occurrences of each of these candidates, and presto you're done.
这里的关键洞见是，Select，尤其是在资本化时，有一个特殊的含义:它引用了在未排序的数组中找到第k个最大条目的问题。也许有点出乎意料的是，这可以在线性时间内完成，例如，使用一个与QuickSelect算法相结合的5中pi投票策略。所以，如果你选择- - -大写字母n/9, 2n/9，…条目(成本:9*线性-这是线性的)，你肯定会发现任何一个出现n/8次的条目。然后再次遍历您的数组，以计算每个候选的出现次数，并显示您已经完成了。
#1
0
The key insight here is that Select, especially when capitalised, has a special meaning: it references the problem of finding the kth largest entry in an unsorted array. Perhaps somewhat surprisingly a priori, this can be done in linear time, for example using a median-of-5 pivoting strategy in combination with the QuickSelect algorithm. So if you Select-with-an-uppercase-S the n/9, 2n/9, ... entries (cost: 9*linear - which is linear), you definitely find any entries that occur n/8 times. Then iterate through your array again to count the number of occurrences of each of these candidates, and presto you're done.
这里的关键洞见是，Select，尤其是在资本化时，有一个特殊的含义:它引用了在未排序的数组中找到第k个最大条目的问题。也许有点出乎意料的是，这可以在线性时间内完成，例如，使用一个与QuickSelect算法相结合的5中pi投票策略。所以，如果你选择- - -大写字母n/9, 2n/9，…条目(成本:9*线性-这是线性的)，你肯定会发现任何一个出现n/8次的条目。然后再次遍历您的数组，以计算每个候选的出现次数，并显示您已经完成了。