169. 多数元素

image.png

统计法

使用 map 统计每个元素的出现次数
时间复杂度：O(n)，空间复杂度：O(n)

执行用时：11 ms, 在所有 Java 提交中击败了26.13%的用户 内存消耗：43.8 MB, 在所有 Java 提交中击败了78.06%的用户

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         if (nums.length == 0) return -1;
  5.         Map<Integer, Integer> map = new HashMap<>();
  6.         for (int num : nums) {
  7.             map.put(num, map.getOrDefault(num, 0) + 1);
  8.         }
  10.         Map.Entry<Integer, Integer> majorityEntry = null;
  11.         for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  12.             if (majorityEntry == null || majorityEntry.getValue() < entry.getValue())
  13.                 majorityEntry = entry;
  14.         }
  15.         return majorityEntry.getKey();
  16.     }
  17. }

排序法

题目说明了众数出现次数大于 n/2 所以排序后下标为 n/2 的元素一定是众数
时间复杂度：O(nlogn)，空间复杂度：跟排序算法有关

执行用时：2 ms, 在所有 Java 提交中击败了61.25%的用户 内存消耗：43.9 MB, 在所有 Java 提交中击败了73.21%的用户

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         Arrays.sort(nums);
  4.         return nums[nums.length / 2];
  5.     }
  6. }