p****3
发帖数: 448 | 1 但我还是没给出欧嗯的答案
unordered array of size N, already know more than half of the elements are
number x (duplicate). the rest of the array is unknown.
find the number x efficiently (that means O(N)) |
T**********r
发帖数: 52 | 2 boyer-moore majority vote algorithm
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
【在 p****3 的大作中提到】
: 但我还是没给出欧嗯的答案
: unordered array of size N, already know more than half of the elements are
: number x (duplicate). the rest of the array is unknown.
: find the number x efficiently (that means O(N))
|
f*****e
发帖数: 2992 | 3 反证法，can't end with other elements.
【在 T**********r 的大作中提到】
: boyer-moore majority vote algorithm
: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
|
w**z
发帖数: 8232 | 4 仰慕你的签名。
【在 T**********r 的大作中提到】
: boyer-moore majority vote algorithm
: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
|
h*****n
发帖数: 188 | 5 search for the N/2 th smallest element in O(N)
【在 p****3 的大作中提到】
: 但我还是没给出欧嗯的答案
: unordered array of size N, already know more than half of the elements are
: number x (duplicate). the rest of the array is unknown.
: find the number x efficiently (that means O(N))
|
t********x
发帖数: 81 | 6 有个疑问
如果数组是 AAABBC,那么用这个算法，最后结果是?0
这怎么办？
【在 T**********r 的大作中提到】
: boyer-moore majority vote algorithm
: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
|
h*****3
发帖数: 1391 | 7 more than half...
【在 t********x 的大作中提到】
: 有个疑问
: 如果数组是 AAABBC,那么用这个算法，最后结果是?0
: 这怎么办？
|
