<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the</em> <code>k<sup>th</sup></code> <em>largest element in the array</em>.</p>

<p>Note that it is the <code>k<sup>th</sup></code> largest element in the sorted order, not the <code>k<sup>th</sup></code> distinct element.</p>

<p>Can you solve it without sorting?</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [3,2,1,5,6,4], k = 2
<strong>Output:</strong> 5
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [3,2,3,1,2,4,5,5,6], k = 4
<strong>Output:</strong> 4
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

static const bool Booster = [](){
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return true;
}();

std::vector<int> parse_input_data_string(const std::string& s) {
    std::vector<int> data_1D;
    const int N = s.size();
    int accumulator = 0;
    bool is_positive = true;;
    for (int i = 1; i < N; ++i) {
        switch (s[i]) {
        case ',':
            data_1D.push_back((is_positive ? accumulator : -accumulator));
            accumulator = 0;
            is_positive = true;
            break;
        case ']':
            data_1D.push_back((is_positive ? accumulator : -accumulator));
            break;
        case '-':
            is_positive = false;
            break;
        default:
            accumulator = accumulator * 10 + (s[i] - '0');
            break;
        }
    }
    return data_1D;
}

int findKthLargest(std::vector<int>& nums, int k) {
    const int N = nums.size();
    const auto b = nums.begin();
    const auto e = nums.end();
    if (k < N / 2) {
        std::nth_element(b, b + k - 1, e, std::greater<int>());
        return nums[k - 1];
    } else {
        std::nth_element(b, e - k, e);
        return nums[N - k];
    }
}

bool Solve = [](){
    std::ofstream out("user.out");
    for (std::string s; std::getline(std::cin, s);) {
        std::vector<int> nums = parse_input_data_string(s);
        std::getline(std::cin, s);
        const int k = std::stoi(s);
        out << findKthLargest(nums, k) << "\n";
    }
    out.flush();
    exit(0);
    return true;
}();
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
    return 0;  
    }
};
14800