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.

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`
• `-231 <= nums[i] <= 231 - 1`

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

C++ 解法一：

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

Java 解法一：

``````public class Solution {
public int majorityElement(int[] nums) {
int res = 0, cnt = 0;
for (int num : nums) {
if (cnt == 0) {res = num; ++cnt;}
else if (num == res) ++cnt;
else --cnt;
}
return res;
}
}
``````

C++ 解法二：

``````class Solution {
public:
int majorityElement(vector<int>& nums) {
int res = 0, n = nums.size();
for (int i = 0; i < 32; ++i) {
int ones = 0, zeros = 0;
for (int num : nums) {
if (ones > n / 2 || zeros > n / 2) break;
if ((num & (1 << i)) != 0) ++ones;
else ++zeros;
}
if (ones > zeros) res |= (1 << i);
}
return res;
}
};
``````

Java 解法二：

``````public class Solution {
public int majorityElement(int[] nums) {
int res = 0, n = nums.length;
for (int i = 0; i < 32; ++i) {
int ones = 0, zeros = 0;
for (int num : nums) {
if (ones > n / 2 || zeros > n / 2) break;
if ((num & (1 << i)) != 0) ++ones;
else ++zeros;
}
if (ones > zeros) res |= (1 << i);
}
return res;
}
}
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/169

Majority Element II

https://leetcode.com/problems/majority-element/

https://leetcode.com/problems/majority-element/discuss/51613/O(n)-time-O(1)-space-fastest-solution

https://leetcode.com/problems/majority-element/discuss/51612/6-Suggested-Solutions-in-C++-with-Explanations

https://leetcode.com/problems/majority-element/discuss/51611/Java-solutions-(sorting-hashmap-moore-voting-bit-manipulation).

https://leetcode.com/problems/majority-element/discuss/51828/C++-solution-using-Moore's-voting-algorithm-O(n)-runtime-comlexity-an-no-extra-array-or-hash-table

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation