Question

169. Majority Element

中文文档

Description

Given an array nums of size n, return _the majority element_.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

 

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

 

Follow-up: Could you solve the problem in linear time and in O(1) space?

Solutions

Solution 1: Moore Voting Algorithm

The basic steps of the Moore voting algorithm are as follows:

Initialize the element $m$ and initialize the counter $cnt = 0$. Then, for each element $x$ in the input list:

1. If $cnt = 0$, then $m = x$ and $cnt = 1$;
2. Otherwise, if $m = x$, then $cnt = cnt + 1$, otherwise $cnt = cnt - 1$.

In general, the Moore voting algorithm requires two passes over the input list. In the first pass, we generate the candidate value $m$, and if there is a majority, the candidate value is the majority value. In the second pass, we simply compute the frequency of the candidate value to confirm whether it is the majority value. Since this problem has clearly stated that there is a majority value, we can directly return $m$ after the first pass, without the need for a second pass to confirm whether it is the majority value.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

class Solution:
  def majorityElement(self, nums: List[int]) -> int:
    cnt = m = 0
    for x in nums:
      if cnt == 0:
        m, cnt = x, 1
      else:
        cnt += 1 if m == x else -1
    return m

class Solution {
  public int majorityElement(int[] nums) {
    int cnt = 0, m = 0;
    for (int x : nums) {
      if (cnt == 0) {
        m = x;
        cnt = 1;
      } else {
        cnt += m == x ? 1 : -1;
      }
    }
    return m;
  }
}

class Solution {
public:
  int majorityElement(vector<int>& nums) {
    int cnt = 0, m = 0;
    for (int& x : nums) {
      if (cnt == 0) {
        m = x;
        cnt = 1;
      } else {
        cnt += m == x ? 1 : -1;
      }
    }
    return m;
  }
};

func majorityElement(nums []int) int {
  var cnt, m int
  for _, x := range nums {
    if cnt == 0 {
      m, cnt = x, 1
    } else {
      if m == x {
        cnt++
      } else {
        cnt--
      }
    }
  }
  return m
}

function majorityElement(nums: number[]): number {
  let cnt: number = 0;
  let m: number = 0;
  for (const x of nums) {
    if (cnt === 0) {
      m = x;
      cnt = 1;
    } else {
      cnt += m === x ? 1 : -1;
    }
  }
  return m;
}

impl Solution {
  pub fn majority_element(nums: Vec<i32>) -> i32 {
    let mut m = 0;
    let mut cnt = 0;
    for &x in nums.iter() {
      if cnt == 0 {
        m = x;
        cnt = 1;
      } else {
        cnt += if m == x { 1 } else { -1 };
      }
    }
    m
  }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  let cnt = 0;
  let m = 0;
  for (const x of nums) {
    if (cnt === 0) {
      m = x;
      cnt = 1;
    } else {
      cnt += m === x ? 1 : -1;
    }
  }
  return m;
};

public class Solution {
  public int MajorityElement(int[] nums) {
    int cnt = 0, m = 0;
    foreach (int x in nums) {
      if (cnt == 0) {
        m = x;
        cnt = 1;
      } else {
        cnt += m == x ? 1 : -1;
      }
    }
    return m;
  }
}

class Solution {
  /**
   * @param Integer[] $nums
   * @return Integer
   */
  function majorityElement($nums) {
    $m = 0;
    $cnt = 0;
    foreach ($nums as $x) {
      if ($cnt == 0) {
        $m = $x;
      }
      if ($m == $x) {
        $cnt++;
      } else {
        $cnt--;
      }
    }
    return $m;
  }
}