跳到主要内容

元素TopK

2024年04月09日
柏拉文
越努力，越幸运

一、最小的 K 个数​

输入整数数组 arr , 找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例1:

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例2:

输入：arr = [0,1,2,1], k = 1
输出：[0]

1.1 快排思想​

思路: 根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k ，若 true 则直接返回此时数组的前 k 个数字即可。

  • getLeastNumbers() 函数：
    • 若 k 大于数组长度，则直接返回整个数组；
    • 执行并返回 quick_sort() 即可；
  • quick_sort() 函数：
    • 哨兵划分: 划分完毕后，基准数为 arr[i] ，左 / 右子数组区间分别为 [l,i−1], [i+1,r]
    • 递归或返回:
      • 若 k < i ，代表第 k + 1 小的数字在 左子数组 中，则递归左子数组；
      • 若 k > i ，代表第 k + 1 小的数字在 右子数组 中，则递归右子数组；
      • 若 k = i ，代表此时 arr[k] 即为第 k + 1 小的数字，则直接返回数组前 k 个数字即可；
function quickSort(array, start, end,k) {
  let left = start;
  let right = end;
  let pivot = array[left];
  while (left < right) {
    while (left < right && array[right] > pivot) {
      right--;
    }
    while (left < right && array[left] <= pivot) {
      left++;
    }
    [array[left], array[right]] = [array[right], array[left]];
  }
  [array[start], array[left]] = [array[left], array[start]];
  if(left > k){
    quickSort(array, start, right - 1,k);
  }
  if(left < k){
    quickSort(array, left + 1, end,k);
  }
  return array.slice(0,k)
}

function getLeastNumbers(array,k){
  if(k === 0 || array.length === 0){
    return [];
  }
  return quickSort(array,0,array.length-1,k);
}

性能分析:

  • 时间复杂度：期望为 O(n)
  • 空间复杂度：期望为 O(logn)

二、前 K 个高频元素​

给你一个整数数组 nums 和一个整数 k,请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。

示例1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例2:

输入: nums = [1], k = 1
输出: [1]

进阶: 你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

2.1 快排思想​

实现

function quickSort(array, start, end, k) {
  let left = start;
  let right = end;
  let pivot = array[left][1];
  while (left < right) {
    while (left < right && array[right][1] < pivot) {
      right--;
    }
    while (left < right && array[left][1] >= pivot) {
      left++;
    }
    [array[left], array[right]] = [array[right], array[left]];
  }
  [array[start], array[left]] = [array[left], array[start]];
  if (left > k) {
    quickSort(array, start, right - 1, k);
  }
  if (left < k) {
    quickSort(array, left + 1, end, k);
  }
  return array.slice(0, k);
}

function topKFrequent(array, k) {
  const map = new Map();
  for (let item of array) {
    map.set(item, map.has(item) ? map.get(item) + 1 : 1);
  }
  const arrayOfFrequent = [...map.entries()];
  if (k >= arrayOfFrequent.length) {
    return [...map.keys()];
  }
  const result = quickSort(arrayOfFrequent, 0, arrayOfFrequent.length - 1, k);
  return [...new Map(result).keys()];
}

三、数组中的第 K 个最大元素​

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

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

3.1 快排思想​

思路: 根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k-1 大的数字 ，那么此时基准数左边的所有数字便是题目所求的 最大的 k 个数 。根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k-1 ，若 true 则直接返回此时数组的 k-1 元素即可。

  • findKthLargest() 函数:

    • 若 k 大于数组长度，则直接返回整个数组

    • 执行并返回 quick_sort() 即可

  • quick_sort() 函数:

    • 哨兵划分: 划分完毕后，基准数为 arr[i] ，左 / 右子数组区间分别为 [l,i−1], [i+1,r]

    • 递归或返回:

      • 若 k-1 < i ，代表第 k 大的数字在 左子数组 中，则递归左子数组；
      • 若 k-1 > i ，代表第 k 大的数字在 右子数组 中，则递归右子数组；
      • 若 k-1 = i ，代表此时 arr[k-1] 即为第 k 大的数字，则直接返回数组前 arr[k-1] 元素即可；
function quickSort(array, start, end,k) {
  let left = start;
  let right = end;
  let pivot = array[left];
  while (left < right) {
    while (left < right && array[right] < pivot) {
      right--;
    }
    while (left < right && array[left] >= pivot) {
      left++;
    }
    [array[left], array[right]] = [array[right], array[left]];
  }
  [array[start], array[left]] = [array[left], array[start]];
  if(left > k-1){
    quickSort(array, start, right - 1,k);
  }
  if(left < k-1){
    quickSort(array, left + 1, end,k);
  }
  return array[k-1]
}

function findKthLargest(array,k){
  if(k === 0 || array.length === 0){
    return [];
  }
  return quickSort(array,0,array.length-1,k);
}

性能分析:

  • 时间复杂度：期望为 O(n)
  • 空间复杂度：期望为 O(logn)