GuilinDev
Lc0169
05 August 2008
169 - Majority Element
原题概述
Given an array of size n, find the majority element. The majority element is the element that appears more than 1
⌊ n/2 ⌋
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
1
2
Input: [3,2,3]
Output: 3
Example 2:
1
2
Input: [2,2,1,1,1,2,2]
Output: 2
题意和分析
给一个非空无序的数组，找到其中的众数，众数是多余元素总个数n/2的数，这个众数一定存在。首先看一下这道题有如下解法：
这里我们选第6个办法 Moore’s voting，大浪淘沙法，维持一个count ，初始化一个数，遍历数组，如果遇到这个数自己，就+1，如果不是自己就-1，当count = 0时，换遍历到的那个数再换一个，最后count ！= 0的数肯定是众数。
代码
投票算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int majorityElement(int[] nums) {
int count = 0, result = 0;
for (int num : nums) {
if (count == 0) {
result = num;
count++;
} else if (result == num) {
count++;
} else {
count--;
}
}
return result;
}
}
位操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int majorityElement(int[] nums) {
int result = 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) result |= (1 << i);
}
return result;
}
}