【python滴滴出行】整数无序数组求第K大数？

题目：给定无序整数序列，求其中第K大的数，例如{45，67，33，21}，第2大数为45。

输入描述:

输入第一行为整数序列，数字用空格分隔，如：45 67 33 21

输入第二行一个整数K，K在数组长度范围内，如：2

输出描述:

输出第K大的数，本例为第2大数：45

code：

def findSmallKnum(arr, k):

    for i in range(k):

        for j in range(i + 1, len(arr)):

            if arr[i] <arr[j]:

                arr[i], arr[j] = arr[j], arr[i]

    return arr[k-1]

if __name__ == "__main__":

    arr = list(map(int, input().split()))#[4, 3, 6, 7,1, 3]

    K = int(input())

    print(findSmallKnum(arr, K))

楼主的样例输出是错的吧。

第二个输入是1 2 3 4.排序后第二个元素应该是2啊

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std

int main()

{

int N,k,i,temp

vector<int>data

vector<int>rank

while(cin>>N>>k,N!=0)

{

for(i=0i<Ni++)

{

cin>>temp

data.push_back(temp)

}

sort(data.begin(),data.end())

rank.push_back(data[k-1])

data.clear()

}

for(i=0i<rank.size()i++)

cout<<rank[i]<<endl

return 0

}

算法描述

设第k个数为标准比a[k-1]大的数放到其左边，比他小的，放到其右边，其中保持a[k-1]是前k个数中最大的值

#include<iostream>

#include<string>

using namespace std

int a[10000]

//寻找前k个数中的最大值

int found(int k){

int i

int max=a[0],flag=0

for(i=0i<ki++)

if(max<a[i]){

max=a[i]

flag=i

}

return flag

}

void change(int &a,int &b){

if(a==b)

return

int t

t=a

a=b

b=t

}

int main()

{

int n,k,i,flag

while(cin>>n>>k){

memset(a,0,sizeof(a))

if(k>n)

continue

for(i=0i<ni++)

cin>>a[i]

flag=found(k)

change(a[flag],a[k-1])

for(i=ki<ni++){

if(a[i]<a[k-1]){

change(a[i],a[k-1])

flag=found(k)

change(a[flag],a[k-1])

}

}

cout<<a[k-1]<<endl

}

return 0

}

---