理想汽车操作系统软件工程师笔试 10-25

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

其中的编程题，应该是软件类公用同一套题，所以是从第一题和第二题选做其一，从第三题和第四题选做其一。核心代码模式。

给定整数数组nums和整数k,请返回数组中第k个最大的元素。

请考虑设计并实现时间复杂度最低的算法。

数组长度为n，1≤k≤n≤10^6，数组中每个元素的值

1≤nums[i]≤10^9

示例1

输入

[3,2,1,5,6,4] 2

输出

5

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[left];
    int i = left + 1, j = right;
    while (true) {
        while (i <= j && nums[i] >= pivot) i++;
        while (i <= j && nums[j] < pivot) j--;
        if (i > j) break;
        swap(nums[i], nums[j]);
    }
    swap(nums[left], nums[j]);
    return j;
}

int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) {
        return nums[left];
    }
    
    int pivotIndex = partition(nums, left, right);
    
    if (k - 1