目录例如流程图示例代码参考资料如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。未排序数组中第 k 个最小/最大元素 预期线性时间(Kth Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time))给定一个数组和一个小于数组大小的数 k我们需要找到数组中第 k 大的元素。已知数组中的所有元素都互不相同。建议您先阅读以下文章然后再阅读本文第k个最小元素C 第k个最小元素 C 第k个最小元素(K’th Smallest Element)-CSDN博客C# 第k个最小元素 C# 第k个最小元素(K’th Smallest Element)-CSDN博客Java 第k个最小元素 Java 第k个最小元素(K’th Smallest Element)_数组中第k小的数 java-CSDN博客Python 第k个最小元素 Python 第k个最小元素(K’th Smallest Element)_最小的 k 个数 python代码-CSDN博客JavaScript 第k个最小元素 JavaScript 第k个最小元素(K’th Smallest Element)-CSDN博客例如输入arr[] {7, 10, 4, 3, 20, 15}k 3输出7输入arr[] {7, 10, 4, 3, 20, 15}k 4输出10在上面的文章(第k个最小元素)中讨论了三种不同的解决方案。本文将讨论方法 4它主要是对上面的文章(第k个最小元素)中讨论的方法 3快速选择的扩展。流程图示例代码# Python3 implementation of above implementation# This function returns kth smallest element# in arr[l..r] using QuickSort based method.# ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCTfrom random import randintdef randomPartition(arr, l, r):n r - l 1pivot randint(1, 100) % narr[l pivot], arr[r] arr[l pivot], arr[r]return partition(arr, l, r)def kthSmallest(arr, l, r, k):# If k is smaller than# number of elements in arrayif (k 0 and k r - l 1):# Partition the array around last element and# get position of pivot element in sorted arraypos randomPartition(arr, l, r)# If position is same as kif (pos - l k - 1):return arr[pos]# If position is more, recur for left subarrayif (pos - l k - 1):return kthSmallest(arr, l, pos - 1, k)# Else recur for right subarrayreturn kthSmallest(arr, pos 1, r,k - pos l - 1)# If k is more than number of elements in arrayreturn 10**9# Standard partition process of QuickSort().# It considers the last element as pivot and# moves all smaller element to left of it# and greater elements to rightdef partition(arr, l, r):x arr[r]i lfor j in range(l, r):if (arr[j] x):arr[i], arr[j] arr[j], arr[i]i 1arr[i], arr[r] arr[r], arr[i]return i# Driver Codearr [12, 3, 5, 7, 4, 19, 26]n len(arr)k 3print(Kth smallest element is,kthSmallest(arr, 0, n - 1, k))# This code is contributed by Mohit Kumar输出Kth smallest element is 5时间复杂度 O(N * log N)。辅助空间 O(1)。参考资料C 第k个最小元素 C 第k个最小元素(K’th Smallest Element)-CSDN博客C# 第k个最小元素 C# 第k个最小元素(K’th Smallest Element)-CSDN博客Java 第k个最小元素 Java 第k个最小元素(K’th Smallest Element)_数组中第k小的数 java-CSDN博客Python 第k个最小元素 Python 第k个最小元素(K’th Smallest Element)_最小的 k 个数 python代码-CSDN博客JavaScript 第k个最小元素 JavaScript 第k个最小元素(K’th Smallest Element)-CSDN博客如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。
