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

问题描述

多数元素是指出现次数大于数组总长度一半的元素,如数组[1,3,3,3,5,7,3],数组长度为7,元素3出现了4次,大于7/2=3,所以元素3为多数元素。

遍历计数法

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}));
  }
}

使用一个HashMap存储每一个元素和它出现的次数。

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

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}));
  }
}

以数组[1,3,3,3,5,7,3]为例,元素3为多数元素,3的二进制表示为

00000000 00000000 00000000 00000011

那么在0位和1位这两个位置的1一定比0多,因为元素3已经占一半以上了。

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

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}));
  }
}

核心原理就是,假设有A,B两个国家,A人口占总人口的一半以上,那么只要A国一个人能够消耗掉B国一个人,最后剩下的一定是A国人,就算B国人内斗也不影响最终结果。
带入到代码中,以数组[1,3,3,3,5,7,3]为例,元素1为B国人,元素3为A国人,最终对拼消耗之后还剩一个3。
以数组[1,1,2,2,3,3,3,3,3]为例,1,2元素都属于B国人,刚开始就是1和2相互消耗(内斗),最后剩下的还是3。

对拼消耗

参考

算法设计:寻找多数元素
[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?