A majority element is an element that appears more that n/2 times.
My initial throught was to:
My inittial Running time would be O(n^n), because it needs to touch each element once for each element. Is there a better algorithm for my problem?
Step 1: Start with the first element. (Take every unique element) in the sorted array and count how many times each occurs.
Step 2: Store a count. If the count of another unique element is greater that count. Store that element and its count.
Step3: After traversing the entire list, compare count to n/2. If count is larger that n/2, there exists a majority element.
Example:
1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 7, 7, 9, 10
**Stored Element = Stored count**
1 = 1
2 = 1
3 = 1
4 = 1
5 = 9
6 = 1
7 = 2
9 = 1
10 = 1
After traversing, 5 = 9. Is count > n/2?
9 > 16/2, Yes. Therefore there is a majority element.
2007-02-05
07:30:22
·
5 answers
·
asked by
roberto1502
1