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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/array/169.majority-element.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.