BFE.devAI解答 - JavaScript 代码题
45. 在未排序的数组中找到第K大的元素

一种解法是使用快速排序的思想，不过不需要对整个数组进行完整的排序，只需要不断地将比第K大的元素小的数排在数组左边，大的数排在右边，直到找到了第K大的数即可。

具体实现过程：

1. 以数组最后一个元素作为基准值，将数组中比该元素大的数都放在该元素的右边，比该元素小的数都放在该元素的左边，可以使用双指针法。
2. 判断该基准值的下标是否为K-1，如果是则返回该值，如果不是则根据下标关系在左边或右边继续递归查找第K大的元素。

代码实现如下：

function findKthLargest(nums, k) {  const swap = (a, b) => {    [nums[a], nums[b]] = [nums[b], nums[a]];  };  const partition = (left, right) => {    const pivotIndex = right;    let i = left;    for (let j = left; j < right; j++) {      if (nums[j] >= nums[pivotIndex]) {        swap(i, j);        i++;      }    }    swap(i, pivotIndex);    return i;  };  const quickSelect = (left, right) => {    if (left === right) return nums[left];    const pivotIndex = partition(left, right);    if (pivotIndex === k - 1) {      return nums[pivotIndex];    } else if (pivotIndex > k - 1) {      return quickSelect(left, pivotIndex - 1);    } else {      return quickSelect(pivotIndex + 1, right);    }  };  return quickSelect(0, nums.length - 1);}// Example:console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // Output: 5console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // Output: 4

时间复杂度为O(n)到O(n^2)，最好的情况下只需要排序一侧，复杂度为O(n)；最差的情况下每次基准值都是数组中最小或最大的数，需要排除所有元素，复杂度为O(n^2)。但由于该算法进行了一些优化，例如随机选取基准值，所以平均情况下时间复杂度为O(n)。