Given input integer array arr of length n, find and return the majority number. Majority number is the element which occurs more than n/2 times. Assume that the input array contains a majority number for sure. Use Moore’s voting algorithm.
| Input Parameters |
Expected outputs |
| arr={ 0,1,0,0,1,2,0}
|
Majority number is 0
|
| arr={2,2,2,2,2,2,1,1,0,0,0}
|
Majority number is 2
|
| arr={1,2,2}
|
Majority number is 2
|
| The java method should accept following input parameters: arr (int array).
|
| Initialize two int variables number and cnt with value 0.
|
| Iterate through arr using a for loop using loop variable idx:
If cnt=0; set number=arr[idx], increment cnt by 1.
If arr[idx]=number, increment cnt by 1.
If arr[idx] !=number, decrement cnt by 1.
|
| At end of for loop, number contains the majority element.
|
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class ArrayFindMajorityElement {
public int arrayFindMajorityNumber(int[] arr) throws Exception{
int number=0; int cnt=0;
for (int idx=0; idx< arr.length; idx++) {
if (cnt==0) {
number=arr[idx];
cnt++;
}else if (arr[idx]==number) {
cnt++;
}else {
cnt--;
}
}
return number;
}
public static void main(String[] args) {
ArrayFindMajorityElement ap=new ArrayFindMajorityElement();
int num;
try {
int[] intArray1 = {0,1,0,0,1,2,0};
printArraySummary(intArray1, "Original Array1:");
num=ap.arrayFindMajorityNumber(intArray1);
System.out.println("Majority number is "+num);
int[] intArray2 = {2,2,2,2,2,2,1,1,0,0,0};
printArraySummary(intArray2, "Original Array1:");
num=ap.arrayFindMajorityNumber(intArray2);
System.out.println("Majority number is "+num);
int[] intArray3 = {1,2,2};
printArraySummary(intArray3, "Original Array1:");
num=ap.arrayFindMajorityNumber(intArray3);
System.out.println("Majority number is "+num);
}catch (Exception exception) {
System.out.print("Exception,"+ exception);
exception.printStackTrace();
}
}
public static void printArraySummary(int[] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("************************************************************************");
System.out.print(label+" : ");
int arrayIndex=0;
for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
System.out.print(intArray[arrayIndex]);
if (arrayIndex< intArray.length-1) {System.out.print(",");}
}
System.out.println();
System.out.println("*************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
}