iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
自我挑戰組

試煉之地 Leetcode 的挑戰系列 第 14

Leetcode 挑戰 Day 14 [169. Majority Element]

169. Majority Element


今天我們一起挑戰leetcode第169題Majority Element!

題目


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.

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

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

今天的題目比較單純,這題是希望我們把題目給我們的一個整數陣列中,找到某個數是出現最多次的,並回傳那個數。而且題目保證出現最多次數的數會出現超過陣列長度的一半。

HahsMap


這題也能透過HashMap的手法,以key存放數字,value存放數字出現個數,加上比對每個數字出現個數,如果超過陣列長度的一半,就回傳該數字,以此來達成題目的要求。

以下是python的程式碼

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dit = {}
        for i in nums:  # 數字:出現個數
            if i not in dit:
                dit[i] = 1
            else:
                dit[i] += 1
        length = len(nums)
        for i in dit:  # 走訪字典,逐一檢查
            if dit[i] > (length) * 0.5:
                return i

以下是C++的程式碼,與上面解法不同是,在這段程式碼中,在建立字典的同時就持續檢查,因此不需要在完成後再走訪一次HashMap。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> dit;
        for(int num:nums){
            if(++dit[num] > nums.size() / 2)  #建立加上檢查
                return num;
        }
    return 0;
    }
};

參考資料

https://leetcode.com/problems/majority-element/discuss/51612/C%2B%2B-6-Solutions


上一篇
Leetcode 挑戰 Day 13 [13. Roman to Integer]
下一篇
Leetcode 挑戰 Day 15 [27. Remove Element]
系列文
試煉之地 Leetcode 的挑戰19

尚未有邦友留言

立即登入留言