Given an array of n integers, where one element appears more than n/2 times. We need to find that element in linear time and constant extra space.

Don’t need to worry about the case when there are no elements with freq > m/2. There are multiple ways to solve the problem.

One approach is Find the median, it takes O(n) on an unsorted array(Kth smallest element approach). Since more than n/2 elements are equal to the same value, the median is equal to that value as well.

Another approach is Majority Counting Algorithm.

public class Majority {

public static int FindMostFrequentElement(int[] sequence)

{

int best = 0;

int count = 0;

for(int element:sequence)

{

if (count == 0)

{

best = element;

count = 1;

}

else

{

// Vote current choice up or down

count += (best == element) ? 1 : -1;

}

}

return best;

}

public static void main(String[] args) {

int [] A = {7,11,8,11,11,9,11,7,11,8,11,9,11};

System.out.println("Majority Element is"+FindMostFrequentElement(A));

}

}

## No comments:

Post a Comment