Python 第k个最小元素(K’th Smallest Element)

目录【朴素方法】使用排序——时间复杂度为 O(n log(n))空间复杂度为 O(1)【预期方法】使用最大堆 - 时间复杂度为 O(n * log(k))空间复杂度为 O(k)【替代方案 1】使用快速选择【替代方案 2】使用计数排序如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个整数数组arr[]和元素个数k求数组中第 k 小的元素。注意k 始终小于数组的大小。例如输入arr[] [10, 5, 4, 3, 48, 6, 2, 33, 53, 10], k 4输出5说明给定数组中第四小的元素是 5。输入arr[] [7, 10, 4, 3, 20, 15], k 3输出7说明给定数组中第三小的元素是 7。【朴素方法】使用排序——时间复杂度为 O(n log(n))空间复杂度为 O(1)其思路是对给定的数组进行排序并返回索引 k - 1 处的元素。def kthSmallest(arr, k):# Sort the given vectorarr.sort()# Return kth element in the sorted vectorreturn arr[k - 1]if __name__ __main__:arr [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]k 4print(kthSmallest(arr, k))输出5【预期方法】使用最大堆 - 时间复杂度为 O(n * log(k))空间复杂度为 O(k)其思路是在遍历数组的过程中维护一个大小为 k 的最大堆。该堆始终包含目前为止遇到的 k 个最小元素。如果堆的大小超过 k则移除最大的元素。最终堆中只保留 k 个最小元素。import heapqdef kthSmallest(arr, k):# Create a max heappq []# Iterate through the array elementsfor i in range(len(arr)):# Push the current element onto the max heapheapq.heappush(pq, -arr[i])# If the size of the max heap exceeds k,#remove the largest elementif len(pq) k:heapq.heappop(pq)return -pq[0]if __name__ __main__:arr [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]k 4print(kthSmallest(arr, k))输出5【替代方案 1】使用快速选择主要思路是利用快速选择QuickSelect函数找到第 k 大元素。具体做法是选择一个基准元素然后将数组分割成多个部分使得大于基准元素的元素位于左侧小于基准元素的元素位于右侧。如果基准元素最终位于索引 k-1 处则该元素即为第 k 大元素。否则我们递归地仅在包含第 k 大元素的左侧或右侧部分进行搜索。def partition(arr, left, right):# Choose the last element as pivotpivot arr[right]i left# Traverse the array and move elements pivot to the leftfor j in range(left, right):if arr[j] pivot:# Swap current element with element at iarr[i], arr[j] arr[j], arr[i]i 1# Place the pivot in its correct positionarr[i], arr[right] arr[right], arr[i]return i# QuickSelect function: recursively finds k-th smallestdef quickSelect(arr, left, right, k):if left right:# Partition around pivotpivotIndex partition(arr, left, right)# Found k-th smallestif pivotIndex k:return arr[pivotIndex]elif pivotIndex k:return quickSelect(arr, left, pivotIndex - 1, k)else:return quickSelect(arr, pivotIndex 1, right, k)return -1def kthSmallest(arr, k):return quickSelect(arr, 0, len(arr) - 1, k - 1)if __name__ __main__:arr [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]k 4print(kthSmallest(arr, k))输出5时间复杂度 最坏情况下为O(n² )但平均时间为 O(n log n)且性能优于基于优先级队列的算法。辅助空间 最坏情况下递归调用栈为 O(n)。平均而言O(log n)。【替代方案 2】使用计数排序主要思路是利用计数排序的频率计数来跟踪有多少元素小于或等于每个值然后直接从这些累积计数中识别出第 K 小的元素而无需对数组进行完全排序。注意这种方法在元素范围较小时特别有效因为我们声明的数组大小为最大元素个数。如果元素范围非常大计数排序方法可能并非最有效的选择。def kthSmallest(arr, k):# First, find the maximum element in the listmaxElement arr[0]for i in range(1, len(arr)):if arr[i] maxElement:maxElement arr[i]# Create a frequency array for each elementfreq [0] * (maxElement 1)for i in range(len(arr)):freq[arr[i]] 1# Keep track of cumulative frequency to find k-th smallestcount 0for i in range(maxElement 1):if freq[i] ! 0:count freq[i]if count k:# If we have seen k or more elements,# return the current elementreturn ireturn -1if __name__ __main__:arr [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]k 4print(kthSmallest(arr, k))输出5时间复杂度 O(n maxElement)其中 maxElement 为数组中的最大元素。辅助空间 O(maxElement)。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。