[Leetcode] Kth Largest Element 풀어보기

https://leetcode.com/problems/kth-largest-element-in-an-array/description/?utm_source=chatgpt.com

Kth Largest Element in an Array - LeetCode

 

오늘은 배열 내부에서 K번째로 큰 원소를 찾는 알고리즘을 구현해보았습니다.

---

1번 방법

 

Array내부에서 k번째로 큰 원소를 찾기위해서는 정렬 후 찾는 것이 가장 간편할 것입니다.

기본적으로 std::sort를 사용하면 O(nlogn)의 복잡도를 가진 방법을 구현할 수 있습니다. 

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.rbegin(), nums.rend());
        return nums[k - 1];
    }
};

---

2번 방법

 

정렬된 값을 항상 유지하고 싶다면 priority queue를 사용해서 vector를 유지하면 될 것입니다.

이를 이용하면, vector를 순회하면서 k크기의 원소만 남도록 최소힙을 구성해 정렬에 필요한 비용보다는 줄일 수 있을 것입니다.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;

        for (auto num : nums)
        {
            int size = pq.size();

            pq.push(num);

            if (size == k)
            {
                pq.pop();
            }

        }
        int ans = pq.top();
        return ans;
    }
};

---

3, 4번 방법

 

n번째 값만 찾는 것이라면 꼭 모두 정렬할 필요는 없을 것입니다. quicksort와 비슷하게 구성하고 필요한 쪽만 정렬한다면 (pivot으로 나눈 양쪽 중 한쪽만 정렬) 정렬 속도가 빨라질 것으로 예상됩니다.

https://basaeng.tistory.com/117

[알고리즘 알아보기] QuickSort

 

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int target = nums.size() - k;

        int left = 0;
        int right = nums.size() - 1;

        while (left <= right)
        {
            int pivotIndex = partition(nums, left, right);

            if (pivotIndex == target)
                return nums[pivotIndex];
            else if (pivotIndex < target)
                left = pivotIndex + 1;
            else
                right = pivotIndex - 1;
        }

        return -1;
    }

    int partition(vector<int>& nums, int left, int right)
    {
        int pivot = nums[right];
        int storeIndex = left;

        for (int i = left; i < right; ++i)
        {
            if (nums[i] < pivot)
            {
                swap(nums[i], nums[storeIndex]);
                ++storeIndex;
            }
        }

        swap(nums[storeIndex], nums[right]);

        return storeIndex;
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int target = nums.size() - k;

        int left = 0;
        int right = nums.size() - 1;

        while (left <= right)
        {
            int pivotIndex = left + rand() % (right - left + 1);
            int pivot = nums[pivotIndex];

            int low = left;
            int cur = left;
            int high = right;

            while (cur <= high)
            {
                if (nums[cur] < pivot)
                {
                    swap(nums[cur], nums[low]);
                    ++cur;
                    ++low;
                }
                else if (nums[cur] > pivot)
                {
                    swap(nums[cur], nums[high]);
                    --high;
                }
                else
                {
                    ++cur;
                }
            }

            if (target < low)
            {
                right = low - 1;
            }
            else if (target > high)
            {
                left = high + 1;
            }
            else
            {
                return nums[target];
            }
        }

        return -1;
    }
};

다만 기본적인  quicksort인 가장오른쪽 값을 pivot으로 잡는 lomuto의 경우 굉장히 성능이 안좋게 나와

이를 개선하고자 3-way partition을 적용했습니다. pivot또한 랜덤으로 잡으니 성능이 굉장히 개선되었습니다.

---

5번 방법

대부분의 C++유저가 알고있을 만한 nth_element를 사용했습니다.

문제에 정확하게 부합되는 알고리즘을 사용한 함수이기 때문에 당연히 가장 좋은 성능을 보였습니다.

내부에서는 마치 sort처럼 현재 array에 상황에 따라 적절한 quicksort를 사용하는 방식입니다.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int target = nums.size() - k;

        nth_element(
            nums.begin(),
            nums.begin() + target,
            nums.end()
        );

        return nums[target];
    }
};

 

---

전체 성능입니다.

알고리즘은 제발 사서드세요

 

하지만 구현해보는 것도 좋겠죠