Be the first user to complete this post
|
Add to List |
234. Majority Element – Part 1
Objective: Given an array of integer write an algorithm to find the majority element in it (if exist).
Majority Element: If an element appears more than n/2 times in array where n is the size of the array.
Example:
int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; Output: No element appearing more than n/2 times
Click here to read O(n) approach-Boyer–Moore majority vote algorithm
Approach 1: Brute Force
Use nested for loops and count each element and if count>n/2 for each element.
Time Complexity: O(n^2)
public class Main {
public static void find(int [] arrA){
boolean found = false;
for (int i = 0; i <arrA.length ; i++) {
int x = arrA[i];
int count = 1;
for (int j = i+1; j <arrA.length ; j++) {
if(x==arrA[j])
count++;
}
if(count>arrA.length/2) {
System.out.println("Element appearing more than n/2 times: " + x);
found = true;
}
}
if(!found)
System.out.println("No element appearing more than n/2 times");
}
public static void main(String[] args) {
int [] arrA = {1,3,5,5,5,5,4,1,5};
find(arrA);
}
}
def find_majority_element(arr):
found = False
for i in range(len(arr)):
x = arr[i]
count = 1
for j in range(i + 1, len(arr)):
if x == arr[j]:
count += 1
if count > len(arr) / 2:
print("Element appearing more than n/2 times:", x)
found = True
if not found:
print("No element appearing more than n/2 times")
if __name__ == "__main__":
arrA = [1, 3, 5, 5, 5, 5, 4, 1, 5]
find_majority_element(arrA)
package main
import (
"fmt"
)
func findMajorityElement(arrA []int) {
found := false
for i := 0; i < len(arrA); i++ {
x := arrA[i]
count := 1
for j := i + 1; j < len(arrA); j++ {
if x == arrA[j] {
count++
}
}
if count > len(arrA)/2 {
fmt.Println("Element appearing more than n/2 times:", x)
found = true
}
}
if !found {
fmt.Println("No element appearing more than n/2 times")
}
}
func main() {
arrA := []int{1, 3, 5, 5, 5, 5, 4, 1, 5}
findMajorityElement(arrA)
}
Approach 2: Hash Map
- Store the count of each element in Hash map.
- Iterate through hash map and check if any element has count >n/2
Time Complexity: O(n), Space Complexity: O(n)
import java.util.*;
public class Main {
public static void find(int [] arrA){
boolean found = false;
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i <arrA.length ; i++) {
if(map.containsKey(arrA[i])){
int count = map.get(arrA[i]);
map.put(arrA[i],++count);
}else
map.put(arrA[i],1);
}
Set set = map.keySet();
Iterator<Integer> iterator = set.iterator();
while (iterator.hasNext()){
int key = iterator.next();
if(map.get(key)>arrA.length/2){
System.out.println("(Hashing)Element appearing more than n/2 times: " + key);
found = true;
break;
}
}
if(!found)
System.out.println("No element appearing more than n/2 times");
}
public static void main(String[] args) {
int [] arrA = {1,3,5,5,5,5,4,1,5};
find(arrA);
}
}
def find_majority_element(arrA):
found = False
element_count = {}
for num in arrA:
if num in element_count:
element_count[num] += 1
else:
element_count[num] = 1
for key, value in element_count.items():
if value > len(arrA) / 2:
print("(Hashing) Element appearing more than n/2 times:", key)
found = True
break
if not found:
print("No element appearing more than n/2 times")
if __name__ == "__main__":
arrA = [1, 3, 5, 5, 5, 5, 4, 1, 5]
find_majority_element(arrA)
package main
import "fmt"
func findMajorityElement(arrA []int) {
found := false
elementCount := make(map[int]int)
for _, num := range arrA {
if _, ok := elementCount[num]; ok {
elementCount[num]++
} else {
elementCount[num] = 1
}
}
for key, value := range elementCount {
if value > len(arrA)/2 {
fmt.Println("(Hashing) Element appearing more than n/2 times:", key)
found = true
break
}
}
if !found {
fmt.Println("No element appearing more than n/2 times")
}
}
func main() {
arrA := []int{1, 3, 5, 5, 5, 5, 4, 1, 5}
findMajorityElement(arrA)
}
Approach 3: Sorting
- Sort array, this will bring all the same elements together.
- Iterate through array and check if any element has count >n/2
Time Complexity: O(nlogn), Space Complexity: O(1)
import java.util.*;
public class Main {
public static void find(int [] arrA){
if(arrA.length==0)
return;
boolean found = false;
Arrays.sort(arrA);
int count = 1;
int x = arrA[0];
for (int i = 1; i <arrA.length ; i++) {
if(x==arrA[i]){
count++;
if(count>arrA.length/2) {
System.out.println("(Sorting)Element appearing more than n/2 times: " + x);
found = true;
break;
}
}else{
x = arrA[i];
count = 1;
}
}
if(!found)
System.out.println("No element appearing more than n/2 times");
}
public static void main(String[] args) {
int [] arrA = {1,3,5,5,5,5,4,1,5};
find(arrA);
}
}
def find_majority_element(arrA):
if len(arrA) == 0:
return
found = False
arrA.sort()
count = 1
x = arrA[0]
for i in range(1, len(arrA)):
if x == arrA[i]:
count += 1
if count > len(arrA) // 2:
print("(Sorting) Element appearing more than n/2 times:", x)
found = True
break
else:
x = arrA[i]
count = 1
if not found:
print("No element appearing more than n/2 times")
if __name__ == "__main__":
arrA = [1, 3, 5, 5, 5, 5, 4, 1, 5]
find_majority_element(arrA)
package main
import (
"fmt"
"sort"
)
func findMajorityElement(arrA []int) {
if len(arrA) == 0 {
return
}
found := false
sort.Ints(arrA)
count := 1
x := arrA[0]
for i := 1; i < len(arrA); i++ {
if x == arrA[i] {
count++
if count > len(arrA)/2 {
fmt.Println("(Sorting) Element appearing more than n/2 times:", x)
found = true
break
}
} else {
x = arrA[i]
count = 1
}
}
if !found {
fmt.Println("No element appearing more than n/2 times")
}
}
func main() {
arrA := []int{1, 3, 5, 5, 5, 5, 4, 1, 5}
findMajorityElement(arrA)
}
Output:
Element appearing more than n/2 times: 5