如何找出数组中第k小的数？

轩辕小不懂发布于 2022-03-28 11:39

阅读 478

答案 1

分类：人工智能

给定一个整数数组，如何快速地求出该数组中第k小的数。假如数组为[4,0,1,0,2,3]，那么第3小的元素是1。

Nen 2022-03-28 14:07

- 程序员

方法一：排序法

最简单的方法就是首先对数组进行排序，在排序后的数组中，下标为k-1的值就是第k小的数。例如：对数组[4,0,1,0,2,3]进行排序后的序列变为[0,0,1,2,3,4]，第3小的数就是排序后数组中下标为2对应的数：1。由于最高效的排序算法（例如快速排序）的平均时间复杂度为O(Nlog2N)，因此，此时该方法的平均时间复杂度为O(Nlog2N)，其中，N为数组的长度。

方法二：部分排序法

由于只需要找出第k小的数，因此，没必要对数组中所有的元素进行排序，可以采用部分排序的方法。具体思路为：通过对选择排序进行改造，第一次遍历从数组中找出最小的数，第二次遍历从剩下的数中找出最小的数（在整个数组中是第二小的数），第k次遍历就可以从N-k+1（N为数组的长度）个数中找出最小的数（在整个数组中是第k小的）。这种方法的时间复杂度为O(N×k)。当然也可以采用堆排序进行k趟排序找出第k小的值。

如何找出数组中第k小的数？

轩辕小不懂的其他提问

类似问题

如何找出数组中第k小的数？

轩辕小不懂 的其他提问

类似问题

轩辕小不懂的其他提问