Leetcode/src/KthLargestElem/program.cpp at master · robling/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include "../include/prevector.h"
#include "../include/presort.h"

//e - s >= 3
//too slow
inline void putMiddleToEnd(std::vector<int>& nums, size_t s, size_t e)
{
    auto it_b = nums.begin();
    std::vector<decltype(it_b)> a = {it_b + s, it_b + std::floor((e - s) / 2 + 0.5), it_b + e};
    int i = 0, min_s = 0, max_s = 0;
    while (i++ != 2){
        if (a[i][0] < a[min_s][0]) min_s = i;
        if (a[i][0] > a[max_s][0]) max_s = i;
    }
    i = 0;
    while(i != 2){
        if (i != min_s && i != max_s) break;
        i++;
    }
    std::swap(a[i][0], a[2][0]);
}

inline void twoSort(std::vector<int>& nums, size_t s){
    if (nums[s] > nums[s + 1]) std::swap(nums[s], nums[s + 1]);
}

inline size_t quickSortCore(std::vector<int>& nums, size_t s, size_t e)
{
    //putMiddleToEnd(nums, s, e);
    auto mid = nums[e];
    size_t i = s, j = s;
    while (j <= e) {
        if (nums[j] <= mid){
            std::swap(nums[i], nums[j]);
            i++, j++;
            continue;
        }
        j++;
    }
    return i - 1;
}

void quickSort(std::vector<int>& nums, size_t s, size_t e)
{
    auto m = quickSortCore(nums, s, e);
    //if (m < s || m > e) return;
    if (m - s > 2) quickSort(nums, s, m - 1);
    else if (m - s == 2) twoSort(nums, s);
    if (e - m > 2) quickSort(nums, m + 1, e);
    else if (e - m == 2) twoSort(nums, m + 1);
}

void startQuickSort(std::vector<int>& nums, size_t s, size_t e)
{
    if (s == e) return;
    if (e - s == 1) {
        twoSort(nums, s);
        return;
    }
    quickSort(nums, s, e);
}

int findKthLargest(vector<int>& nums, int k)
{
    //convert to k min's index
    k = nums.size() - k;
    size_t s = 0,  e = nums.size() - 1;
    auto m = quickSortCore(nums, s, e);
    while (k != m) {
        s = (k < m) ? s : m + 1;
        e = (k < m) ? m - 1 : e;
        m = quickSortCore(nums, s, e);
    }
    return nums[k];
}

int Mymain()
{
    std::vector<int> nums;
    GenerateRandomArray(nums, 10001);
    auto nums_s = nums;
    int k = 1539;
    int myk = 0, stdk = 2;
    {TIC
        //startQuickSort(nums, 0, nums.size() - 1);
        myk = findKthLargest(nums, k);
    TOC}
    {TIC
        std::sort(nums_s.begin(), nums_s.end());
        stdk = nums_s[nums.size() - k];
    TOC}
    cout << "Check increase : " << std::boolalpha << CheckSorted(nums, nIncrease) << std::noboolalpha << endl;
    cout << "Check K Largest : " << std::boolalpha << (myk == stdk) << std::noboolalpha << endl;
    return 0;
}