[LeetCode] Majority Element

169. Majority Element

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.

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

  • Time : O(n)
  • Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cnt = 0, res;
for(auto& n : nums) {
if(!cnt) res = n;
cnt += (res == n ? 1 : -1);
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/09/PS/LeetCode/majority-element/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.