[LeetCode 笔记] 169. Majority Element

前言

　　这题目的逻辑是找出阵列中出现次数过半的元素，这里有使用一层 for 迴圈遍历整个阵列后，用 HashMap 来操作存储查找，Map 时间可以视为常数时间，时间複杂度可以达到 O(n)，这里有 JAVA 和 Python 的写法。

题目

Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

给定一个阵列 nums 大小为 n，回传这个出现多次的元素。
这个出现多次的元素，出现超过半数。你可以认为这个出现多次的元素总是在这个阵列里。

题目连结：https://leetcode.com/problems/majority-element/

题目限制

n == nums.length
1 <= n <= 5 * 104
109 <= nums[i] <= 109

範例

Input: nums = [3,2,3]Output: 3

Input: nums = [2,2,1,1,1,2,2]Output: 2

思路&笔记

遍历阵列里所有的元素把元素和次数存在 Map 里 ( key：value )当下已有的元素，把 key 的次数 ( value ) +1把 Map 里次数 (value) 大于阵列一半的 key 回传

JAVA 实现

class Solution {    public int majorityElement(int[] nums) {              Map<Integer, Integer> isMap = new HashMap<Integer, Integer>();        int ret=0;                // foreach 写法，类型 int 遍历后把 nums 里的每个值丢进 num        for (int num: nums) {            if (!isMap.containsKey(num)) // 如果没找到指定的 key                isMap.put(num, 1); // (key:value) 添加进 map            else                isMap.put(num, isMap.get(num)+1); // 找到指定的 key 的 value 后 +1            if (isMap.get(num)>nums.length/2) { // 如果当下的 key 的 value 大于阵列长度的一半                ret = num;                break;            }        }        return ret;    }}

JAVA 进阶实现

笔者还在学习中，参考了在讨论区里网友一致认同的超简单解法。

class Solution {    public int majorityElement(int[] nums) {        Arrays.sort(nums); // 重新排序 (小到大)    return nums[nums.length / 2]; // 因重新排序后，获取阵列中间的元素，一定是超过半数的元素    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution(object):    def majorityElement(self, nums):        """        :type nums: List[int]        :rtype: int        """        dic = {} # 空字典        # 字典里找寻 key (索引n)，如果找不到 key 的话，把阵列里的索引 n 添加进字典当 key# 把次数 0+1 添加进去当 value        for n in nums:            dic[n] = dic.get(n, 0) + 1 # {索引n:0+1}            if dic[n] > len(nums)//2: # 判断当前的 key 的值，有无大于阵列的一半                return n # 回传当前的 key

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/04/23/LeetCode-169-Majority-Element-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论