LeetCode #169 Majority Element

問題概要

入力値：nums(int array)
出力値：int
return the majority element of nums.
問題のリンク

入力例

x: [2,2,1,2]
answer: 2

解答例1

Hash Map
計算量：O(n)
Python

from collections import defaultdict

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num_count = defaultdict(int)
        for num in nums:
            num_count[num] += 1
        sorted_nums = sorted(num_count.items(), key=lambda x:x[1], reverse=True)
        return sorted_nums[0][0]

Runtime: 152ms
Beats: 91.26%

C++

#include <map>

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::map<int, int> num_count;
        for (int num : nums) {
            if (num_count.contains(num)) {
                num_count[num] += 1;
            } else {
                num_count[num] = 1;
            }
        }
        int result = 0;
        int current_count = 0;
        for (auto count : num_count) {
            if (count.second > current_count) {
                result = count.first;
                current_count = count.second;
            }
        }
        return result;
    }
};

Runtime: 23ms
Beats: 21.92%