查找数组中的第K大数（未完）

写在前面的一些话

本文通过一个小问题，用多种方式解答，其中涉及到的算法不会去详细介绍，所以请看之前要有一定的算法基础，如：排列，二分等

问题

描述

设数组 A[0..N-1] 存在 N 个无序整数，找到数组 A 中的第 K（1≤K≤N） 大数。注意：结果是顺序排序后的第 K 个最大的元素，而不是第 K 个不同的最大元素。

示例

输入：A=[4,2,6,7,1,3] K=3
输出：3

随机数组

为了方便起见，还是写个随机生成数组的函数。

const randomAry = (n = 10, range = { min: 1, max: 99 }) => {
  let arr = Array.from({ length: n });
  arr = arr.map(() => {
    return Math.floor(Math.random() * (range.max - range.min + 1) + range.min);
  });
  // 去重
  arr = Array.from(new Set(arr));
  console.log(`random - ${arr}`);
  return arr;
};
let array = randomAry();

思路

1. Array.prototype.sort()

利用javascript中的sort()函数，对数组元素从大到小排序。
由于不同的js引擎对sort()的实现不同，所以不能保证排序的时间和空间复杂度。

const findKth = (arr, K) => {
  arr.sort((a, b) => b - a);
  return { arr: arr, K: arr[K - 1] };
};
let result = findKth(array, 3);
// { arr: [ 91, 86, 70, 62, 61, 56, 47, 42, 38 ], K: 70 }

选择排序

• 每次从剩余数组元素中找到最大的元素，并将其从数组中剔除，知道进行到K次操作。时间复杂度 0(n²)。

/**
 * @Description: 每次从剩余数组元素中找到最大的元素，并将其从数组中剔除，知道进行到K次操作
 * @param { Array }: 随机数组
 * @param { Number }: 查找的第K数
 * @return { Object }:{arr:排列完的数组元素,K:第K最大} 
 */
const findKthC = (arr, K) => {
  let i = 0;
  while (i <= K) {
    if (!arr.length) break;
    let j = 0;
    for (let index = 0; index < arr.length; index++) {
      if (arr[index] > arr[j]) {
        j = index;
      }
    }
    if (i === K - 1) return arr[j];
    arr.splice(j, 1);
    i += 1;
  }
};
// { arr: [ 79, 69, 56, 50, 39, 23, 22, 8 ], K: 79 }

• 选择排序过程中，把每次查找到的数组元素最大元素添加到一直排序序列A[0...i-1]的末尾。

/**
 * @Description: 选择排序过程中，把每次查找到的数组元素最大元素添加到一直排序序列A[0...i-1]的末尾
 * @param { Array }: 随机数组
 * @param { Number }: 查找的第K数
 * @return { Object }:{arr:排列完的数组元素,K:第K最大} 
 */
const findKthC_1 = (arr, K) => {
  for (let i = 0; i < arr.length - 1; i++) {
    let max = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] > arr[max]) {
        max = j;
      }
    }
    [arr[i], arr[max]] = [arr[max], arr[i]];
  }
  return { arr: arr, K: arr[K - 1] };
};
// { arr: [ 96, 85, 73, 44, 34, 31, 21, 20, 13, 4 ], K: 73 }

有空在写 其他排序