**Presume the majority exists**, the following algo use O(1) space and
only scan the array one pass.
It is simple idea of counting. If there exists a majority elements in
the array, it must be the remaining element on the counter after we
consider all elements.
int getMajority(int A[], int n){
1)Take a look at Quick Sort, especially how the partition works.
2)Try to write an algo to select the kth smallest element in an
unsorted array.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks