# 在一个数组中寻找多数元素(Find most elements in an array)-其他

## 在一个数组中寻找多数元素(Find most elements in an array)

### 遍历计数法

``````import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

class Solution {

public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > (nums.length / 2)) {
return entry.getKey();
}
}
return -1;
}

public static void main(String[] args) {
System.out.println(new Solution().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
}
}
``````

### 排序取中项法(前提存在多数元素)

``````import java.util.Arrays;

class Solution {

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

public static void main(String[] args) {
System.out.println(new Solution().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
}
}
``````

### 使用位运算(前提存在多数元素)

``````class Solution {

public int majorityElement(int[] nums) {
int res = 0;
int 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;
}
//num在第i位的值，如3在第0位的值为1，num&(1<<i)的结果要么为0，要么为(1<<i)
int bit = num & (1 << i);
if (bit == 0) {
zeros++;
} else {
ones++;
}
}
if (ones > zeros) {
//将res的第i位置为1，如将3的第2位置为1，就变成了7
res |= (1 << i);
}
}
return res;
}

public static void main(String[] args) {
System.out.println(new Solution().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
}
}
``````

``````00000000 00000000 00000000 00000011
``````

### 摩尔投票法(前提存在多数元素)

``````class Solution {

public int majorityElement(int[] nums) {
int count = 0;
int res = 0;
for (int num : nums) {
if (count == 0) {
count = 1;
res = num;
} else {
if (res == num) {
count++;
} else {
count--;
}
}
}
return res;
}

public static void main(String[] args) {
System.out.println(new Solution().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
}
}
``````

``对拼消耗``

### 参考

[LeetCode] 169. Majority Element 求大多数

————————

### Problem description

Most elements refer to elements that appear more than half the total length of the array, such as array [1,3,3,3,5,7,3]. The length of the array is 7, and element 3 appears four times, which is greater than 7 / 2 = 3, so element 3 is most elements.

### Ergodic counting method

``````import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

class Solution {

public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > (nums.length / 2)) {
return entry.getKey();
}
}
return -1;
}

public static void main(String[] args) {
System.out.println(new Solution().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
}
}
``````

Use a HashMap to store each element and the number of times it appears.

### Sorting median method (provided that there are most elements)

``````import java.util.Arrays;

class Solution {

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

public static void main(String[] args) {
System.out.println(new Solution().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
}
}
``````

In an ordered array, the elements between them must be most elements (if any).

### Use bit operations (provided that most elements exist)

``````class Solution {

public int majorityElement(int[] nums) {
int res = 0;
int 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;
}
//num在第i位的值，如3在第0位的值为1，num&(1<<i)的结果要么为0，要么为(1<<i)
int bit = num & (1 << i);
if (bit == 0) {
zeros++;
} else {
ones++;
}
}
if (ones > zeros) {
//将res的第i位置为1，如将3的第2位置为1，就变成了7
res |= (1 << i);
}
}
return res;
}

public static void main(String[] args) {
System.out.println(new Solution().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
}
}
``````

Taking the array [1,3,3,3,5,7,3] as an example, element 3 is the majority element, and the binary representation of 3 is

``````00000000 00000000 00000000 00000011
``````

Then there must be more 1 than 0 in the two positions of 0 and 1, because element 3 already accounts for more than half.

### Moore voting method (provided there is a majority of elements)

``````class Solution {

public int majorityElement(int[] nums) {
int count = 0;
int res = 0;
for (int num : nums) {
if (count == 0) {
count = 1;
res = num;
} else {
if (res == num) {
count++;
} else {
count--;
}
}
}
return res;
}

public static void main(String[] args) {
System.out.println(new Solution().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
}
}
``````

The core principle is that if there are two countries a and B, and the population of a accounts for more than half of the total population, as long as one person in country a can consume one person in country B, the rest must be people in country a, and even the internal struggle of people in country B will not affect the final result.
Bring it into the code. Take the array [1,3,3,3,5,7,3] as an example. Element 1 is from country B and element 3 is from country A. finally, there is a 3 left after the pairing consumption.
Take the array [1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3] as an example. The elements of 1 and 2 belong to the people of country B. at the beginning, 1 and 2 consume each other (internal fighting), and finally 3 is left.

``对拼消耗``

### reference resources

Algorithm design: find most elements
[LeetCode] 169. Majority element
How to understand Moore voting algorithm?