有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
要求:时间复杂度 ,空间复杂度
数据范围:, ,数组中每个元素满足
有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
[1,3,5,2,2],5,3
2
[10,10,9,9,8,7,5,6,4,3,4,2],12,3
9
去重后的第3大是8,但本题要求包含重复的元素,不用去重,所以输出9
# -*- coding:utf-8 -*- class Solution: def findKth(self, a, n, K): if n>=K and K>=1: l = self.order(a) o=l[::-1] return o[K-1] else: return def order(self, tinput): if len(tinput) < 2: return tinput else: temp = tinput[0] less = [i for i in tinput[1:] if i <= temp] more = [i for i in tinput[1:] if i > temp] return self.order(less) + [temp] + self.order(more)
class Solution: def findKth(self, a, n, K): a.sort(reverse =True) return a[K-1]
# -*- coding:utf-8 -*- class Solution: def quick_sort(self,a,left,right,k): if left < right: mid = self.partition(a,left,right) if mid < k: self.quick_sort(a,left,mid-1,k) elif mid > k: self.quick_sort(a,mid+1,right,k) else: return a else: return a def partition(self,a,left,right): pivot = left while left != right: while left < right and a[right] > a[pivot]: right -= 1 while left < right and a[left] <= a[pivot]: left += 1 if left < right: a[left],a[right] = a[right],a[left] a[pivot],a[left] = a[left],a[pivot] return left def findKth(self, a, n, K): # write code here return self.quick_sort(a,0,n-1,n-K)[n-K]
# -*- coding:utf-8 -*- class Solution: def quick_sort(self,a,left,right,k): mid = self.partition(a,left,right) if mid == k: return a[mid] elif mid > k: return self.quick_sort(a,left,mid-1,k) elif mid < k: return self.quick_sort(a,mid+1,right,k) def partition(self,a,left,right): pivot = left while left != right: while left < right and a[right] > a[pivot]: right -= 1 while left < right and a[left] <= a[pivot]: left += 1 if left < right: a[left],a[right] = a[right],a[left] a[pivot],a[left] = a[left],a[pivot] return left def findKth(self, a, n, K): # write code here return self.quick_sort(a,0,n-1,n-K)
# -*- coding:utf-8 -*- class Solution: def findKth(self, a, n, K): # write code here def quick_sort(nums,K): if len(nums)<=1: return nums pivot=nums[0] left=quick_sort([x for x in nums if x<pivot],K) right=quick_sort([x for x in nums if x>pivot],K) return left+[pivot]+right nums=quick_sort(a,K) return nums[n-K]
class Solution: def findKth(self, a, n, K): # write code here low,high = 0,n-1 return self.fastSort(a,K,low,high) def fastSort(self,a,k,low,high): mid = self.partition(a,low,high) if(mid+1==k): return a[mid] if(mid+1>k): return self.fastSort(a,k,low,mid-1) return self.fastSort(a,k,mid+1,high) def partition(self,a,low,high): mid = a[low] while(low<high): while(low<high and a[high]<=mid): high -= 1 a[low]=a[high] while(low<high and a[low]>=mid): low+=1 a[high]=a[low] a[low] = mid return low
# 比较清晰易懂的Python完成 # -*- coding:utf-8 -*- def partition(a, low, high): i = (low-1) # index of smaller element pivot = a[high] # pivot for j in range(low, high): if a[j] <= pivot: i = i+1 a[i], a[j] = a[j], a[i] a[i+1], a[high] = a[high], a[i+1] return (i+1) def quickSort(a, low, high): if len(a) == 1: return a if low < high: pi = partition(a, low, high) quickSort(a, low, pi-1) quickSort(a, pi+1, high) while True: try: x=input().replace(']', '') x=x.replace('[', '') x=list(x.split(',')) k=int(x.pop()) n=int(x.pop()) a=list(map(int,x)) quickSort(a, 0, n-1) a = a[::-1] #注意这里要求从大到小排列 我刚开始没有注意到 print(a[k-1]) except:break
class Solution: def findKth(self, a, n, K): # write code here if n == 1: return a[0] a,index = self.fastorder(a,n) if index == K: return a[index-1] elif index < K: return self.findKth(a[index:], len(a[index:]), K-index) elif index > K: return self.findKth(a[:index-1], len(a[:index-1]), K) def fastorder(self,a,n): if n == 1: return a,n left = 0 right = n-1 val = a[0] while left<right: while left<right: if a[right]>val: a[left] = a[right] break else: right -= 1 while left<right: if a[left]<val: a[right]=a[left] break else: left += 1 a[left] = val return a,left+1调了半天怎么都不对,最后发现题目要求是第K大,我写的是第K小,mmp