Title:
Majority Element
Link to LeetCode:
https://leetcode.com/problems/majority-element/
Specification:
Given an array of size n, find the majority element.
The majority element is the element that appears more than n/2 times.
You may assume that the array is non-empty and the majority element always exist in the array.
Examples:
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
Initial Code and Signature:
public interface ElementFinder {
public int majorityElement(int[] nums);
}
Algorithm:
Run-Time Complexity Analysis
O (number of elements) * (read each element + put or update each element in the map ) = O(n) * O (1) = O (n)
GitHub Project:
https://github.com/m-h-s/Algorithms-Codes/tree/master/29%20-%20MajorityElement
Code:
/**
* @author Mahsa Sadi
*
* @since 2020 - 05 - 26
*
* License Creative Commons
*
* Copyright by Mahsa Sadi
*
*/
import java.util.*;
public class ElementFinderS1 implements ElementFinder {
/**
*
*
* Problem: Majority Element
*
*
* Description:
*
* Given an array of size n, find the majority element.
* The majority element is the element that appears more than n/2 times.
* You may assume that the array is non-empty and the majority element always exist in the array.
*
*
* Solution:
*
* 1- Consider a frequency table which records the frequency of the observed element.
* 2- For each element in the array, record and update the frequency of that element.
* 3- If the frequency of an element exceeds the length of the array divided by two, that element is the majority element.
*
* Time Complexity: O (n)
*
*
*
*/
@Override
public int majorityElement(int[] nums) {
int majorityElement = -1;
Map stat = new HashMap ();
int i = 0;
boolean found = false;
while (i < nums.length && !found)
{
int count = 1;
if (stat.containsKey(nums[i]))
count = stat.get(nums[i]) + 1;
stat.put(nums [i], count);
if (count > nums.length / 2)
{
majorityElement = i;
found = true;
}
i++;
}
return nums [majorityElement];
}
}