求包含n个整数的数组A的第i小的数

小鱼儿 2023-07-12 14:21 8阅读 0赞

# 题目：求包含n个整数的数组A的第i小的数。 #

解法一：排序

将数组A从小到大排序，之后第i个数即为所求。

时间复杂度为O(n²)

解法二：**维护一个长度为i的有序数组B\[i\]（顺序为从小到大），遍历A\[j\],每遍历到一个元素将其与B中的最大元素（即B中最后一个元素）作比较，若比B中最大元素大，则继续遍历。否则挤掉最大元素并插入到B中的合适位置，有点类似直插法。**

比如i=3，过程如下：

将前将前三个元素填入数组B中并从小到大排序三个元素填入数

j来遍历A中的其他元素，此时遍历到第四个元素A\[j\]=1，

因为1比12小，故而1将12挤掉，成功跻身目前最三小元素，再根据直插法，依次与前两个元素比较，插入其正确的位置，结         果如下：

当j遍历到第五个元素A\[j\]=24时，因为24比B中最大元素9大，故无法跻身B中，j继续向后遍历：

当j遍历到第六个元素A\[j\]=2时，同理，因为2比9小，9被挤掉，2插入到B中的合适位置

依次类推，B的最终结果为：

此时B中最大元素即为所求，此例中3是数组A中第3小的数。

> 时间复杂度：最坏情况，每一个元素都要与所维护的i个数比较，故时间复杂度为O(ni)，但如果i值比较大，想一种极限情况i趋近n，可能会退化成O(n²),其效果还不如解法一的直接排序O(nlog(n)).

解法三：**维护一个数组的代价过于巨大，我们可以用堆这个数据结构来代替，与解法二的思想类似。**

**维护一个结点数为i的大顶堆（每一个父结点都大于等于其子结点），由性质可得，这个大顶堆存储的是目前的最i小元素，堆顶元素就是这最i小元素中的最大值，即为第i小元素，也是所求。**

具体步骤是：

> （1）根据原数组的前i个元素先创建一个结点数为i的大顶堆。
> 
> （2）依次遍历原数组，同理，若该元素大于等于堆顶元素，则继续遍历；否则用该元素替换堆顶元素，并根据下沉操作其重新调整为大顶堆。
> 
> （3）当原数组遍历完成时，此时的堆顶元素即为所有，第i小元素。

> 复杂度分析：创建堆的时间复杂度为O(i),遍历剩余数组的时间复杂度为O(n-i),每次重新调整堆的时间复杂为O(logi),每次遍历都要重新调整堆，因此总时间复杂度为O((n-i)logi+i)。

解法四：**分治**

**类似于快排，当一次快排完成时，枢纽元素的左侧全是小于等于该元素的，枢纽元素的右侧全是大于该元素的。**

例如，枢纽元素左侧有k个数，则枢纽元素为第k+1小的数。

然后比较k+1与i的大小，

> 若k+1<i,则去枢纽元素的右边继续去分治，此时找的是第\[i-(k+1)\]小元素，因为左边已经抵消了k+1个了。
> 
> 若k+1>i，则去枢纽元素的左边继续去分治，此时找的仍然是第i小元素。
> 
> 若k+1=i，则枢纽元素即是第i小元素。

注意：此题也可延伸为求第i大的数，与求第i小数非常类似。 这里只说明了算法的基本思想，代码读者可以感兴趣实现看看

还没有评论，来说两句吧...