b******b
发帖数: 713 | 1 binary search,
int lowbound = 0, uppbound =n;
int mid = (lowbound + uppbound) / 2;
int countLowHalf=0, countUpperHalf = 0;
now go through the list and count how many in lower half, how many in
upperhalf, and update the low/upper bound to the part which has count > n/2.
since each time we reduce the range by 2, so need longn steps to get to the
bottom, and each step need to loop through the whole array, so it's nlogn.
not sure if there is O(n) algorithm.
n= |
|
