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
class Solution {
public:
    // get Kth biggest value by bubble sort
    int getKthByBubbleSort(vector%3Cint%3E& nums, int startIndex, int endIndex, int k) {
        // simple bubble sort
        for (int i = 0; i < endIndex - startIndex - 1; i++) {
            for (int j = startIndex; j < endIndex - 1 - i; j++) {
                if (nums[j] > nums[j+1]) {
                    swap(nums[j], nums[j+1]);
                }
            }
        }
        return nums[endIndex - k];
    }

    // partition by pivotvalue (smaller values to left, bigger values to right of the pivot)
    pair<int, int> partitionByPivot(vector<int>& nums, int startIndex, int endIndex, int pivotValue) {
        int cursor = startIndex;
        for (int i = startIndex; i < endIndex; i++) {
            if (nums[i] > pivotValue) {
                swap(nums[i], nums[endIndex - 1]);
                endIndex--;
                i--;
            } else if (nums[i] < pivotValue) {
                swap(nums[cursor], nums[i]);
                cursor++;
            }
        }

        int cursorStart = cursor;
        while(cursor < endIndex && nums[cursor] == pivotValue) cursor++;
        int cursorEnd = cursor - 1;
        return make_pair(cursorStart, cursorEnd);
    }

    // get Kth biggest value in O(n)
    int getKthByMedianOfMedians(vector<int>& nums, int startIndex, int endIndex, int k) {
        if (endIndex - startIndex <= 5) {
            return getKthByBubbleSort(nums, startIndex, endIndex, k);
        }

        vector<int> medians;
        for(int i = startIndex; i < endIndex; i += 5) {
            medians.push_back(
                getKthByBubbleSort(nums, 
                                   i,
                                   min(i + 5, endIndex), 
                                   min(3    , ((endIndex - i) / 2) + 1)
                                  )
                             );
        }

        int medianOfMedians = getKthByMedianOfMedians(medians, 0, medians.size(), (medians.size() / 2) + 1);
        // pivot is medianOfMedians
        pair<int, int> indexOfPivot = partitionByPivot(nums, startIndex, endIndex, medianOfMedians); 

        if (indexOfPivot.first <= endIndex - k && endIndex - k <= indexOfPivot.second) {
            return medianOfMedians;
        } else if (indexOfPivot.second < endIndex - k) {
            return getKthByMedianOfMedians(nums, indexOfPivot.second + 1, endIndex, k);
        } else {
            return getKthByMedianOfMedians(nums, startIndex, indexOfPivot.first, k - (endIndex - indexOfPivot.first));
        }
    }
    int majorityElement(vector<int>& nums) {
        return getKthByMedianOfMedians(nums, 0, nums.size(), (nums.size() / 2) + 1);
    }
}