iT邦幫忙

0

[LeetCode 筆記] 169. Majority Element

  • 分享至 

  • xImage
  •  

前言

  這題目的邏輯是找出陣列中出現次數過半的元素,這裡有使用一層 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

(新手上路,如有錯誤請友善告知,感謝)

Blog
https://chris81051.github.io/2023/04/23/LeetCode-169-Majority-Element-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言