[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

成績

---

Language	Runtime	Memory
Java	20 ms	48.5MB
Python	131 ms	14.9MB