[编程题] 寻找第K大

93 阅读 0 评论 62 点赞

我是靠谱客的博主自由保温杯，最近开发中收集的这篇文章主要介绍[编程题] 寻找第K大，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

[编程题] 寻找第K大

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

测试样例：

[1,3,5,2,2],5,3

返回：2

CPP实现：

class Finder {
public:
int findKth(vector<int> a, int n, int K) {
// write code here
int pos = -1;
int startlow = 0;
int starthigh = n-1;
while (pos != K-1) {
int i = startlow;
int j = starthigh;
int pivot = a[i];
while (i < j) {
while(i < j && a[j] >= pivot) j--;
a[i] = a[j];
while(i < j && a[i] <= pivot) i++;
a[j] = a[i];
}
pos = i;
a[pos] = pivot;
if (pos < K-1) {
startlow = pos+1;
} else if (pos > K-1) {
starthigh = pos-1;
}
}
return a[pos];
}
};

Go语言实现：

func main() {
nums := []int{1,3,5,2,2}
n, k = 5, 3
kth := kthNumber(nums, n, k)
fmt.Println(kth)
}
func kthNumber(nums []int, n int, k int) int {
low, high := 0, n-1
pos := -1
for pos != k-1 {
if pos < k-1 {
low = pos + 1
} else if pos > k-1 {
high = pos - 1
}
pos = partition(nums, low, high)
}
return nums[pos]
}