[번외] kth largest element in a array

[junki-kim]

https://leetcode.com/problems/kth-largest-element-in-an-array/

[ajh8894]

[junki-kim]

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        int start = 0;
        int end = nums.size() - 1;
        int kthLargestIndex = nums.size() - k;

        while (start < end)
        {
            int pivotIndex = partition(nums, start, end);

            if (kthLargestIndex == pivotIndex)
            {
                return nums[pivotIndex];
            }
            else if (kthLargestIndex < pivotIndex)
            {
                end = pivotIndex - 1;
            }
            else // k > pivotIndex
            {
                start = pivotIndex + 1;
            }
        }

        return nums[kthLargestIndex];
    }

    // 배열을 랜덤한 pivotIndex 기준으로 양쪽으로 나눔. pivotIndex은 첫번째 값 으로 임의 시정
    int partition(vector<int> &nums, int start, int end)
    {
        int pivotIndex = start;

        printf("partition 시작 start = %d, end = %d\n", start, end);

        while (start <= end)
        {
            // pivotIndex보다 크거나 같은 수 탐색
            while (start <= end && nums[start] <= nums[pivotIndex])
            {
                start++;
            }

            // pivotIndex보다 작은 수 탐색
            while (start <= end && nums[end] > nums[pivotIndex])
            {
                end--;
            }

            if (start > end)
            {
                break;
            }

            printf("i = %d, j = %d 스왑 시작\n", nums[start], nums[end]);
            swap(nums, start, end);
            print(nums);
        }

        printf("pivot과 end 스왑\n");
        swap(nums, pivotIndex, end);
        print(nums);

        // pivotIndex을 리턴
        return end;
    }

    void swap(vector<int> &nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    void print(std::vector<int> const &input)
    {
        for (int i = 0; i < input.size(); i++)
        {
            std::cout << input.at(i) << ' ';
        }

        printf("\n\n");
    }
};

int main()
{
    // static const int arr[] = {1, 5, 1, 1, 6, 4};
    // static const int arr[] = {1, 1, 2, 1, 2, 2, 1};
    // static const int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    static const int arr[] = {5, 6, 2, 9, 7, 3, 4, 1, 8, 10};
    std::vector<int> inputs(arr, arr + sizeof(arr) / sizeof(arr[0]));

    Solution solution;

    printf("소팅 시작\n");
    solution.print(inputs);

    // solution.partition(inputs, 0, inputs.size() - 1);
    // solution.print(inputs);

    int k = 2;
    int kth = solution.findKthLargest(inputs, k);

    solution.print(inputs);
    printf("%d 번째로 큰 수는 %d", k, kth);
}