# 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.

```java
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

```java
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⌊2*n*⌋ (and \lfloor \dfrac{n}{2} \rfloor + 1⌊2*n*⌋+1, incidentally, if n*n* is even).

```java
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.

```java
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 n*n* times, so the algorithm runs in linear time.
* Space complexity : O(1)

  Boyer-Moore allocates only constant additional memory.

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