题目链接

题目描述

image.png

思路

使用 map 遍历，然后再遍历 map，取出 count > n / 3 的即可

  1. public List<Integer> majorityElement(int[] nums) {
  2.     Map<Integer, Integer> map = new HashMap<>(16);
  3.     List<Integer> res = new ArrayList<>();
  5.     for (int num : nums) {
  6.         Integer count = map.getOrDefault(num, 0);
  7.         map.put(num, count + 1);
  8.     }
  9.     for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  10.         if (entry.getValue() > (nums.length / 3)) {
  11.             res.add(entry.getKey());
  12.         }
  13.     }
  14.     return res;
  15. }

image.png
https://leetcode-cn.com/problems/majority-element-ii/solution/qiu-zhong-shu-ii-by-leetcode-solution-y1rn/

  • 额，这个不好描述，建议使用代码调试，非常清晰

    1. public List<Integer> majorityElement(int[] nums) {
    2.   // 先选择备选人，超过n/3的最多有两个
    3.   int element1 = 0;
    4.   int element2 = 0;
    5.   int vote1 = 0;
    6.   int vote2 = 0;
    8.   for (int num : nums) {
    9.       if (vote1 > 0 && num == element1) {
    10.           // 如果该元素为第一个元素，则计数加1
    11.           // elem1 已经被选过，再次遇见，票数加一
    12.           vote1++;
    13.       } else if (vote2 > 0 && num == element2) {
    14.           // 如果该元素为第二个元素，则计数加1
    15.           // elem2 已经被选过，再次遇见，票数加一
    16.           vote2++;
    17.       } else if (vote1 == 0) {
    18.           // elem1 还没有被选，选择当前数作为elem1
    19.           // 选择第一个元素
    20.           element1 = num;
    21.           vote1++;
    22.       } else if (vote2 == 0) {
    23.           // 选择第二个元素
    24.           // elem2 还没有被选，选择当前数作为elem1
    25.           element2 = num;
    26.           vote2++;
    27.       } else {
    28.           // 遇见一个既不属于 elem1，也不属于 elem2 的数，票数都减一
    29.           // 如果三个元素均不相同，则相互抵消1次
    30.           vote1--;
    31.           vote2--;
    32.       }
    33.   }
    35.   int cnt1 = 0;
    36.   int cnt2 = 0;
    37.   for (int num : nums) {
    38.       if (vote1 > 0 && num == element1) {
    39.           cnt1++;
    40.       }
    41.       if (vote2 > 0 && num == element2) {
    42.           cnt2++;
    43.       }
    44.   }
    45.   // 检测元素出现的次数是否满足要求
    46.   List<Integer> ans = new ArrayList<>();
    47.   if (vote1 > 0 && cnt1 > nums.length / 3) {
    48.       ans.add(element1);
    49.   }
    50.   if (vote2 > 0 && cnt2 > nums.length / 3) {
    51.       ans.add(element2);
    52.   }
    54.   return ans;
    55. }