Comment on page
169.Majority-Element
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.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
Intuition
We can exhaust the search space in quadratic time by checking whether each element is the majority element.
Algorithm
The brute force algorithm iterates over the array, and then iterates again for each number to count its occurrences. As soon as a number is found to have appeared more than any other can possibly have appeared, return it.
class Solution {
public int majoritylement(int[] nums) {
int majorityCount = nums.length / 2;
for (int num : nums) {
int count = 0;
for (int elem : nums) {
if (elem == num) {
count += 1;
}
}
if (count > majorityCount) {
return num;
}
}
return -1;
}
}
class Solution {
private Map<Integer, Integer> countNums(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!counts.containsKey(num)) {
counts.put(num, 1);
} else {
int count = counts.get(num);
if (count > nums.length / 2) {
return num;
} else {
counts.put(num, count + 1);
}
}
}
return counts;
}
}
Intuition
If the elements are sorted in monotonically increasing (or decreasing) order, the majority element can be found at index \lfloor \dfrac{n}{2} \rfloor⌊2n⌋ (and \lfloor \dfrac{n}{2} \rfloor + 1⌊2n⌋+1, incidentally, if nn is even).
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
Intuition
If we know the majority element in the left and right halves of an array, we can determine which is the global majority element in linear time.
class Solution {
private int countInRange(int[] nums, int num, int low, int high) {
int count = 0;
for (int i = low; i <= high; i++) {
if (nums[i] == num) count++;
}
return count;
}
private int majorityElementRec(int[] nums, int low, int high) {
if (low == high) return nums[low];
int mid = (high - low) / 2 + low;
int left = majorityElementRec(nums, low, mid);
int right = majorityElementRec(nums, mid + 1, high);
if (left == right) return left;
int leftCount = countInRange(nums, left, low, high);
int rightCount = countInRange(nums, right, low, high);
return leftCount > rightCount ? left : right;
}
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length - 1);
}
}
Complexity Analysis
- Time complexity : O_(_n)Boyer-Moore performs constant work exactly nn times, so the algorithm runs in linear time.
- Space complexity : O(1)Boyer-Moore allocates only constant additional memory.
class Solution{
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
}
}
Last modified 3yr ago