发布时间:2023-09-20 13:30
NC140题:给定一个长度为 n 的数组,请你编写一个函数,返回该数组按升序排序后的结果。
#快速排序
class Solution:
def MySort(self , arr: List[int]) -> List[int]:
self.quick(arr,0,len(arr)-1)
return arr
def quick(self,arr,st,end):
if st>=end: return
left, right = st, end #左右指针
tmp = arr[(st + end) // 2]#基准元素
while left<=right:
while left<=right and arr[left]tmp:#直到找到小于tmp的
right-=1
if left <= right:
arr[left], arr[right] = arr[right], arr[left]
left+=1
right-=1
self.quick(arr,st,right)#对左子组快排
self.quick(arr,left,end)#对右子组快排
各种排序:排序_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896?tpId=196&tqId=37185&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
NC119 题:给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。
#直接排序 取前k个 O(nlog2n) O(1)
#优化 堆排序 O(nlog2k) O(k)
1.将n个数字放入堆中
2.然后如果此时堆中的数字超过k个,那么就说明此时堆中最大的数字一定不属于最小的k个数字里面,所以我们可以将堆顶的元素进行出堆。
3.堆变为数组
import heapq#小根堆
class Solution:
def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
res,q=[],[]
if len(input)k:#保证是k个较小元素在大根堆中
heapq.heappop(q)
for i in range(k):#堆中元素取出入数组
res.append(-1*q[0])
heapq.heappop(q)
return res
NC119 题:有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
#直接排序 O(n*lgn)
class Solution:
def findKth(self , a: List[int], n: int, K: int) -> int:
a.sort(reverse = True)
return a[K-1]
#快速排序:每次移动,可以找到一个标杆元素p,然后将大于它的移到左边,小于它的移到右边。
快排+二分 时间复杂度 O(nlogn),空间复杂度 O(1)
当right-p小于k的时候,在后半部分搜索,
当right-p大于k的时候,在前半部分搜索。
class Solution:
def findKth(self , a: List[int], n: int, k: int) -> int:
return self.find(a,0,n-1,k)
def find(self,a,left,right,k):
p = self.quick(a,left,right)
if p== k-1:
return a[p]
elif p=tmp:#直到找到基准左边小于tmp的
left+=1
a[right]=a[left]
a[left]=tmp
return left