****In Java**** Given an array of integers A, find the Majority Element. Majorit
ID: 3887900 • Letter: #
Question
****In Java****
Given an array of integers A, find the Majority Element.
Majority Element in an array of size N in an element that appears more than N/2 times.
Write a function:
int findMajority(int[] A)
that accepts an array A. The function should return the Majority Element in the array. If no majority element then return 0.
Use following methods to solve the problem:
int findCandidate(int a[])
that accepts the array and find a candidate for the majority
boolean isMajority(int a[], int cand)
that accept the array and the candidate element and check if the candidate occurs more than n/2 times
Input
5
1 2 1 2 2
Where,
First line represents the size of an array.
Second line represents array elements separated by single space.
Output
2
Here for the given array, 2 appears 3 times in the array of size 5.
No space after the element in the output.
Assume that,
N is an integer within the range [1 to 10000].
Array elements are within the range [-2147483648 to 2147483647].
** Use the following driver**
class DriverMain{
public static void main(String args[]){
HW3_P4 hw3P4 = new HW3_P4();
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int A[] = new int[N];
for (int i = 0; i < N; i++) {
A[i] = s.nextInt();
}
System.out.print(hw3P4.findMajority(A));
}
}
** and use the following class HW3_P4 that was refered to in main***
class HW3_P4{
public int findMajority(int[] array){
}
/* Function to find the candidate for Majority */
int findCandidate(int a[]) {
}
/* Function to check if the candidate occurs more than n/2 times */
boolean isMajority(int a[], int cand) {
}
}
Explanation / Answer
Tested on Eclipse
/**********************HW3_P4.java************************/
import java.util.HashMap;
import java.util.Map;
/**
* The Class HW3_P4.
*/
public class HW3_P4 {
/**
* Find majority.
*
* @param array the array
* @return the int
*/
public int findMajority(int[] array) {
Map<Integer, Integer> map = new HashMap<>();
int maxElement = 0;
int count = 0;
for (int i : array) {
if (map.containsKey(i)) {
int value = map.get(i);
map.put(i, ++value);
} else{
map.put(i, 1);
}
}
for (Integer key : map.keySet()) {
if (map.get(key) > count) {
count = map.get(key);
maxElement = key;
}
}
return count > array.length / 2 ? maxElement : 0;
}
/**
* Find candidate.
*
* @param a the a
* @return the int
*/
/* Function to find the candidate for Majority */
int findCandidate(int a[]) {
return findMajority(a);
}
/**
* Checks if is majority.
*
* @param a the a
* @param cand the cand
* @return true, if is majority
*/
/* Function to check if the candidate occurs more than n/2 times */
boolean isMajority(int a[], int cand) {
int count = 0;
for (int i : a) {
if (i == cand) {
count++;
}
}
return count > a.length / 2 ? true : false;
}
}
/************************************DriverMain.java****************************/
import java.util.Scanner;
/**
* The Class DriverMain.
*/
public class DriverMain {
/**
* The main method.
*
* @param args the arguments
*/
public static void main(String args[]) {
HW3_P4 hw3P4 = new HW3_P4();
Scanner s = new Scanner(System.in);
System.out.println("Input");
int N = s.nextInt();
int A[] = new int[N];
for (int i = 0; i < N; i++) {
A[i] = s.nextInt();
}
System.out.println("Output");
System.out.print(hw3P4.findMajority(A));
}
}
/**********************output***********************/
Input
5
1 2 1 2 2
Output
2
Thanks a lot. Please let me know if you have any doubt.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.