编写 Python 程序查找第 K 小元素

问题是一个给定的整数数组，我们需要找到数组中第 K 小的元素，其中 K 是一个小于或等于数组长度的正整数。让我们看下面的例子。

示例 -

输入

输出

k'th smallest array element is 4

输入

输出

k'th smallest array element is 10 

让我们用各种方法来解决这个问题。

方法 1：暴力破解法

在此方法中，我们首先对给定数组进行排序。这里我们将使用冒泡排序算法，并使用列表切片获取第 K 小的元素。让我们理解下面的例子。

示例 -

输出

kth smallest array element is: 7

解释 -

在上面的函数中，我们定义了一个名为 find_k_smallest() 的函数，该函数使用简单的排序方法查找数组中第 K 小的元素。

1. 函数 find_k_smallest 接受三个参数：arr（输入数组）、n（数组的长度）和 k（所需第 K 小元素的索引）。
2. 代码使用嵌套循环对数组执行简单的排序操作。外层循环从第一个元素 (i = 0) 开始迭代数组中的每个元素。
3. 内层循环从 i 开始迭代数组中的剩余元素直到数组末尾。它将索引 i 处的元素与后续元素 (j) 进行比较，以找到最小的元素。
4. 如果索引 i 处的元素大于索引 j 处的元素，则执行交换，将较小的元素移到前面。这样，循环完成后，最小的元素将在索引 i 处（数组的第一个元素）。
5. 外层循环一直持续到达到数组末尾，确保数组按升序排序。
6. 最后，函数从排序后的数组中返回第 K 小的元素。由于数组索引从 0 开始，因此返回索引 k-1 处的元素 (arr[k-1])。

在给定的示例中，输入数组是 [7, 10, 4, 3, 20, 15]，而所需的第 3 小元素是第 3 小的 (k = 3)。运行 find_k_smallest() 函数后，输出将是 7，这是排序数组中的第 3 小元素。

因此，由于用于排序的嵌套循环，此实现的 time complexity 为 O(n²)。但是，我们将优化上述解决方案。

方法 2：使用 sort() 方法

我们将使用内置的 sort() 方法。让我们理解下面的例子。

示例 -

输出

kth smallest array element is: 7

解释 -

函数 find_k_smallest() 接受三个参数：arr（输入数组）、n（数组的长度）和 k（所需第 K 小元素的索引）。

我们使用 sort() 方法将数组按升序排序。这将重新排列数组中的元素，使最小的元素位于索引 0，最大的元素位于最后一个索引。

对数组进行排序后，函数返回索引 k-1 处的元素。由于数组索引从 0 开始，因此第 K 小的元素将位于索引 k-1 处。

上述代码的总体 time complexity 为 O(n log n)，其中 n 是数组的长度。

方法 3：使用最大堆

我们将使用最小堆来解决这个问题。让我们理解下面的例子。

示例 -

输出

kth smallest array element is:7

解释 -

在上面的代码中，我们导入了 heapq 模块来处理堆。然后，我们创建空堆来存储数组的元素。将所有元素推入堆后，我们进入一个循环，提取最小元素 K 次。我们使用 heapq.heappop() 从堆中弹出并检索最小的元素。

kth_smallest 变量在从堆中提取元素时会跟踪第 K 小的元素。

最后，我们返回 kth_smallest 的值，这将是数组中第 K 小的元素。

上述代码的 time complexity 为 O(n)，这是前述代码的优化版本。

方法 4：使用优先级队列

为了使用优先级队列解决查找第 K 小元素的问题，我们可以利用 Python 的 queue 模块，特别是 PriorityQueue 类。以下是使用优先级队列的实现。让我们理解下面的例子。

示例 -

输出

kth smallest array element is: 7

解释 -

在上面的代码中，我们首先从 queue 模块导入 PriorityQueue 类，该类允许我们使用优先级队列。

find_k_smallest 函数接受两个参数：arr（输入数组）和 k（所需第 K 小元素的索引）。我们创建一个 PriorityQueue 类的新的 pq 实例。我们迭代数组中的每个元素，并使用 put() 方法将元素插入优先级队列。

插入元素后，我们检查优先级队列的大小 (pq.qsize()) 是否大于 k。如果是，我们使用 get() 方法从优先级队列中删除最小的元素。这确保了优先级队列在任何给定时间只包含 K 个最小的元素。

处理完所有元素后，我们使用 get() 方法从优先级队列中检索第 K 小的元素。

最后，我们返回检索到的第 K 小的元素。