70 lines
1.6 KiB
Java
70 lines
1.6 KiB
Java
|
//Given an array A of N elements. Find the majority element in the array.
|
|||
|
|
//A majority element in an array A of size N is an element that appears more than N/2 times in the array
|
|||
|
|
|
|||
|
|
// Moore’s Voting Algorithm => Time Complexity: O(n), Space Complexity: O(1)
|
|||
|
|
|
|||
|
|
import java.util.*;
|
|||
|
|
import java.io.*;
|
|||
|
|
import java.lang.*;
|
|||
|
|
|
|||
|
|
class Main {
|
|||
|
|
public static void main(String args[]) {
|
|||
|
|
Scanner sc = new Scanner(System.in);
|
|||
|
|
int t = sc.nextInt();
|
|||
|
|
|
|||
|
|
while(t-- > 0) {
|
|||
|
|
int n =sc.nextInt();
|
|||
|
|
int arr[] = new int[n];
|
|||
|
|
|
|||
|
|
for(int i = 0; i < n; i++)
|
|||
|
|
arr[i] = sc.nextInt();
|
|||
|
|
|
|||
|
|
System.out.println(new Solution().majorityElement(arr, n));
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
class Solution
|
|||
|
|
{
|
|||
|
|
static int majorityElement(int a[], int size){
|
|||
|
|
int cand = findCand(a, size);
|
|||
|
|
if(isMajority(a, size, cand))
|
|||
|
|
return cand;
|
|||
|
|
return -1;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
static int findCand(int arr[], int n){
|
|||
|
|
int max_index=0; int count=1;
|
|||
|
|
for(int i=1; i<n; i++){
|
|||
|
|
if(arr[max_index]==arr[i])
|
|||
|
|
count++;
|
|||
|
|
else count--;
|
|||
|
|
if(count==0){
|
|||
|
|
max_index=i;
|
|||
|
|
count=1;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
return arr[max_index];
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
static boolean isMajority(int arr[], int n, int cand){
|
|||
|
|
int count=0;
|
|||
|
|
for(int i=0; i<n; i++){
|
|||
|
|
if(cand==arr[i])
|
|||
|
|
count++;
|
|||
|
|
}
|
|||
|
|
if(count > n/2) return true;
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/* Test Case:
|
|||
|
|
Input:
|
|||
|
|
N = 5 A[] = {3,1,3,3,2}
|
|||
|
|
|
|||
|
|
Output: 3
|
|||
|
|
|
|||
|
|
Explanation:
|
|||
|
|
Since, 3 is present more
|
|||
|
|
than N/2 times, so it is
|
|||
|
|
the majority element. */
|