admin 管理员组

文章数量: 1087818

[勇者闯LeetCode] 169. Majority Element

[勇者闯LeetCode] 169. Majority Element

Description

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.

Information

  • Tags: Array | Divide and Conquer | Bit Manipulation
  • Difficulty: Easy

Solution

利用位操作,先初始化输出元素为首元素,其出现次数cnt为1,扫描数组,若当前元素与输出元素相同,则cnt加1;否则cnt减1,且cnt为0时,将输出元素重置为当前元素,出现次数cnt重置为1,扫描结束后输出元素将是数组中出现次数超过一半的那个元素。

C++ Code

class Solution {
public:int majorityElement(vector<int>& nums) {int ans = nums[0], cnt = 1;for (const auto& num : nums) {if (num == ans) {++cnt;}else {--cnt;if (cnt == 0) {ans = num;cnt = 1;}}}return ans;}
};

本文标签: 勇者闯LeetCode 169 Majority Element