LeetCode169. 多数元素

2024 年 8 月 24 日 星期六(已编辑)
这篇文章上次修改于 2024 年 8 月 24 日 星期六,可能部分内容已经不适用,如有疑问可询问作者。

LeetCode169. 多数元素

169. 多数元素

给定一个大小为 n 的数组 nums,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

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

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

Java

出现的次数大于一半,则说明排序后的中间那个数一定是出现次数最多的,直接返回即可

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

候选人算法

查看了以前的提交记录,发现使用过哈希表、候选人算法。应该是在练习哈希表的时候做过这题。好吧,再次看到这道题全然想不起以前的解法,说明以前只是看到了但是并没有能深刻理解,无法做到举一反三。

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

哈希表

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            if (!hashMap.containsKey(num)) {
                hashMap.put(num, 1);
            }else {
                hashMap.put(num, hashMap.get(num) + 1);
            }
        }
        for(Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            if (entry.getValue() > nums.length / 2) {
                return entry.getKey();
            }
        }
        return 0;
    }
}
  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...