169.Majority-Element

169. Majority Element

题目地址

https://leetcode.com/problems/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

代码

Approach 1: Brute Force

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;
  }
}

Approach 2: HashMap

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;
  }
}

Approach 3: Sorting

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];
  }
}

Approach 5: Divide and Conquer

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);
  }
}

Approach 5: Boyer-Moore Voting Algorithm

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;
    }
  }
}