# 多数元素

## 题目

• 示例 1：
输入：[3,2,3]


• 示例 2：
输入：[2,2,1,1,1,2,2]



## 思路0-HashMap 次数统计

### java-出现次数最多的

public int majorityElement(int[] nums) {
int result = nums[0];
int maxCount = 1;
Map<Integer, Integer> countMap = new HashMap<>(nums.length);
//O(N)
for(int n : nums) {
int count = countMap.getOrDefault(n,0)+1;
if(count >= maxCount) {
result = n;
maxCount = count;
}
// 统计次数
countMap.put(n, count);
}
// 找到超过一半的元素
return result;
}


Runtime: 9 ms, faster than 31.63% of Java online submissions for Majority Element.
Memory Usage: 44 MB, less than 44.51% of Java online submissions for Majority Element.


### java-次数超过一半

public int majorityElement(int[] nums) {
int limit = nums.length >> 1;
Map<Integer, Integer> countMap = new HashMap<>(limit);
for(int n : nums) {
int count = countMap.getOrDefault(n,0)+1;
if(count > limit) {
return n;
}
countMap.put(n, count);
}
// 异常
return -1;
}


Runtime: 7 ms, faster than 41.56% of Java online submissions for Majority Element.
Memory Usage: 44.4 MB, less than 29.86% of Java online submissions for Majority Element.


## 思路1-排序

### java 实现

public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length >> 1];
}


Runtime: 1 ms, faster than 99.95% of Java online submissions for Majority Element.
Memory Usage: 42 MB, less than 92.66% of Java online submissions for Majority Element.


## 思路2-摩尔投票法

### java 实现

public int majorityElement(int[] nums) {
int major = nums[0];
int count = 1;

for(int i = 1; i < nums.length; i++) {
int num = nums[i];
// 全部抵消，重新赋值
if(count == 0) {
count++;
major = num;
} else if(major == num) {
// 自己阵营，+1
count++;
} else {
// 敌方阵营，-1
count--;
}
}

return major;
}


### 复杂度

Runtime: 1 ms, faster than 99.95% of Java online submissions for Majority Element.
Memory Usage: 42.4 MB, less than 59.78% of Java online submissions for Majority Element.


# 多数元素 II

## 題目

输入：[3,2,3]



输入：nums = [1]



输入：[1,1,1,3,3,2,2,2]



1 <= nums.length <= 5 * 10^4

-10^9 <= nums[i] <= 10^9

## 思路0-HashMap 记数

### java 实现

public List<Integer> majorityElement(int[] nums) {
// 最多两个元素
List<Integer> results = new ArrayList<>(2);
int limit = nums.length / 3;
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums) {
int count = map.getOrDefault(num, 0) + 1;
if(count > limit && !results.contains(num)) {
}
map.put(num, count);
}
return results;
}


Runtime: 8 ms, faster than 29.02% of Java online submissions for Majority Element II.
Memory Usage: 42.3 MB, less than 78.51% of Java online submissions for Majority Element II.


## 优化思路1-摩尔投票法

（1）利用摩尔投票法找到投票最多的 2 個元素

（2）统计两个元素出现的次数，超过 1/3 则加入到结果中

### java 实现

int one = nums[0];
int two = nums[0];
int countOne = 0;
int countTwo = 0;
for(int n : nums) {
// 投票
if(one == n) {
countOne++;
continue;
}
if(two == n) {
countTwo++;
continue;
}
// 第1个候选人配对
if (countOne == 0) {
one = n;
countOne++;
continue;
}
// 第2个候选人配对
if (countTwo == 0) {
two = n;
countTwo++;
continue;
}
// 其他情况，二者都抵消
countOne--;
countTwo--;
}
// 计数阶段
countOne = 0;
countTwo = 0;
for(int n : nums) {
if(n == one) {
countOne++;
} else if(n == two) {
countTwo++;
}
}
int limit = nums.length / 3;
List<Integer> results = new ArrayList<>();
if(countOne > limit) {
}
if(countTwo > limit) {
}
// 添加元素
return results;
}


Runtime: 1 ms, faster than 99.86% of Java online submissions for Majority Element II.
Memory Usage: 43.1 MB, less than 30.73% of Java online submissions for Majority Element II.


## 优化思路2-排序

public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
if (nums.length == 1) {
return res;
} else if (nums.length == 2) {
if (nums[0] == nums[1]) {
return res;
}
return res;
}

// 核心逻辑
quickSort(nums, 0, nums.length - 1, res);

return res;
}

private void quickSort(int[] nums, int start, int end, List<Integer> res) {
int threshold = nums.length / 3;
if (end - start + 1 <= threshold) return;

int pivot = nums[end];
int pos = start - 1;
int count = 1;
for (int i = start; i < end; i++) {
if (nums[i] < pivot) {
swap(nums, ++pos, i);
} else if (nums[i] == pivot) {
swap(nums, pos + count, i);
count++;
}

}

swap(nums, pos + count, end);
if (count > threshold) {
}

quickSort(nums, start, pos, res);
quickSort(nums, pos + count, end, res);
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}


# 参考资料

https://leetcode-cn.com/problems/number-of-digit-one/