leetcode169. 求众数

约定不等于承诺〃 2022-03-31 13:28 260阅读 0赞

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

  1. public int majorityElement(int[] nums) {
  2.    if (1 == nums.length) {
  3.         return nums[0];
  4.     }
  5.     int i;
  6.     int length = nums.length;
  7.     Map<Integer, Integer> map = new TreeMap<>();
  8.     for (i = 0; i < length; i++) {
  9.         map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
  10.     }
  11.     List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
  12.     Collections.sort(list,(o1,o2)->(o2.getValue()-o1.getValue()));
  13.     return list.get(0).getKey();
  14. }

更优秀的方式

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         int length = nums.length;
  4.         if(length == 1) return nums[0];
  5.         int count = 1, maj = nums[0];
  6.         for (int i = 1; i < nums.length; i++) {
  7.             if (count == 0) {
  8.                 maj = nums[i];
  9.             }
  10.             if (maj != nums[i]) {
  11.                 count--;
  12.             } else {
  13.                 count++;
  14.             }
  15.         }
  16.         return maj;
  17.     }
  18. }

更简单的方式

  1. public int majorityElement1(int[] nums) {
  2.             Arrays.sort(nums);
  3.             return nums[nums.length/2];
  4.         }

发表评论

表情：
评论列表 （有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读