面试题目(常考题型)
描述
设数组
A[0..N-1]存在 N 个无序整数，找到数组 A 中的第 K（1≤K≤N） 大数。注意：结果是顺序排序后的第 K 个最大的元素，而不是第 K 个不同的最大元素。
示例
输入：A=[3, 7, 1, 6, 9, 1, 2], K=4
输出：6
答案解析
这道题目实际就是数组排序的变种。只要将数组排序好，就能找到对应的值。下面列出能想到的一些方案：
1. Array.prototype.sort()
利用 JavaScript 标准库中提供的 sort()方法，对数组元素进行从大到小排序。
由于不同的 JavaScript 引擎对 sort() 方法的具体实现不同，因此无法保证排序的时间和空间复杂度。
function findKthLargest(nums, k) {
nums.sort((a, b) => b - a)
return nums[k - 1]
}
2. 选择排序
利用我们生活中最直观的查找方式：每次从数组剩余元素中找到最大的元素，并将其从数组中剔除，直至进行到第 K 次操作。时间复杂度为 O(n^2)。
let i = 0
while (i <= k) {
if (!nums.length) break
let j = 0
for (let index = 0; index < nums.length; index++) {
if (nums[index] > nums[j]) {
j = index
}
}
if (i === k - 1) return nums[j]
nums.splice(j, 1)
i += 1
}
这与选择排序原理非常相似，不同之处在于，选择排序过程中没有将每次查找到的最大元素从数组中剔除，而是把它添加到已排序序列 A[0..i-1] 的末尾。
for (let i = 0; i < nums.length - 1; i++) {
let max = i
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] > nums[max]) {
max = j
}
}
[nums[i], nums[max]] = [nums[max], nums[i]]
}
3. 快速排序
以下这种快速排序的写法，是从 Free Pascal 的 Demo 目录文件中学到的，也一直沿用至今。
平均时间复杂度为 O(nlogn)，为了避免快速排序退化至 O(n^2)，采用了随机化划分基准。
var quickSort = function(arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};
扫一扫 关注我的公众号【前端名狮】，更多精彩内容陪伴你！
