Py这道题感觉过不了。啥方法都用了。

P1923 【深基9.例4】求第 k 小的数

s_a_b_e_ryyds @ 2022-04-26 00:02:25

sort()

n,m=map(int,input().strip().split())
ls=[int(i) for i in input().split()]
ls.sort()
print(ls[m])

快速排序

def MovePivot(arr,low,high):
    Pivot=arr[high]
    imove=low-1
    for i in range(low,high):
        if arr[i]<=Pivot:
            imove+=1
            arr[imove],arr[i]=arr[i],arr[imove]
    arr[imove+1],arr[high]=arr[high],arr[imove+1]
    return imove+1
def QuickSort(arr,low,high):
    if low<high:
        pivot=MovePivot(arr,low,high)
        QuickSort(arr,low,pivot-1)
        QuickSort(arr,pivot+1,high)

n,m=map(int,input().strip().split())
ls=[int(i) for i in input().split()]
QuickSort(ls,0,n-1)
print(ls[m])

归并排序

def MergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid=len(arr)//2
    left=MergeSort(arr[:mid])
    right=MergeSort(arr[mid:])
    return Merge(left,right)
def Merge(left,right):
    r,l=0,0
    temp=[]
    lmax=len(left)
    rmax=len(right)
    while l<lmax and r<rmax:
        if left[l]<=right[r]:
            temp.append(left[l])
            l+=1
        else:
            temp.append(right[r])
            r+=1
    temp+=list(left[l:])
    temp+=list(right[r:])
    return temp
n,m=map(int,input().strip().split())
ls=[int(i) for i in input().strip().split()]
sl=MergeSort(ls)
print(sl[m])

by Mandel520 @ 2022-04-26 06:34:23

Python 中好像没有和 C++ 中的 nth_element() 功能相同的函数, 只能使用 sort() 先排序后再查找第 k 位的数, 由于 Python 中的整数默认是 64 位形式的, 因此在排序时会导致最后两个点 MLE, 因此必须使用 fromstring() 函数把 int 转为 numpy 库中特有的 32 位形式

import numpy as np

n, k = map(int, input().split())
arr = np.fromstring(input(), dtype = np.uint32, sep=' ')
arr.sort()
print(arr[k])

by s_a_b_e_ryyds @ 2022-04-26 14:50:28

@Mandel520 卧草,谢谢。牛逼。


|