(Easy - Sorting) Leetcode - 169. Majority Element

이 문제는 배열이 주어졌을 때 배열에서 과반수를 차지하는 숫자를 찾는 것입니다.

과반수를 차지하는 숫자는 배열의 절반 크기(n/2)보다 많습니다.

 

가장 간단하게 풀 수 있는 방법은 정렬을 한 뒤 Index = n / 2에 있는 수를 반환하는 것입니다.

과반수를 차지하는 숫자를 찾는 것이므로 정렬을 하면 배열의 중간에 과반수를 차지하는 수가 오기에 간단하게 답을 찾을 수 있습니다.

    int majorityElement(std::vector<int> &nums)
    {
        std::sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }

이 방법은 정렬하는 시간으로 인해 평균 시간복잡도 O(N log N)의 시간을 가집니다.

 

HashMap을 사용하면 시간복잡도 O(N)안에 문제를 해겨할 수 있습니다.

    int majorityElement(std::vector<int> &nums)
    {
        unordered_map<int, int> m;
        for (const int& n : nums)
            m[n]++; // 배열에 있는 숫자의 개수
        
        int half = nums.size() / 2;
        for (auto& [key, value] : m)
            if (value > half) // 과반수를 차지하면
                return key;

        return nums[0];
    }

각 배열의 원소의 숫자를 센 후 배열의 절반 크기보다 많은 숫자를 반환해주면 됩니다.