基本資訊

• 難度： Easy
• 網址： https://leetcode.com/problems/majority-element/

演算法與資料結構：

• Hash Table

題意

給予一個陣列，找出其中的主要元素。

主要元素的定義是，出現次數為 n/2 次，而這個主要元素必然會存在。

想法

• 依序走訪紀錄出現次數
• 當出現次數超過個數的一半時就中斷走訪回傳結果

程式碼

class Solution {
    func majorityElement(_ nums: [Int]) -> Int {
        var map = [Int: Int]()
        
        for num in nums {
            let count = (map[num] ?? 0) + 1
            if count > (nums.count / 2) {
                return num
            }
            map[num] = count
        }
        
        return -1
    }
}

複雜度分析

令 n 為陣列的長度

執行結果

• Runtime: 86 ms (Beats 88.37%)
• Memory: 15.84 MB (Beats 30.23%)

結語

以上，就是今天的 LeetCode in Swift ，

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！