NC 寻找第K大
系列文章目录
文章目录
- 系列文章目录
- 前言
前言
前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。
描述
有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
import java.util.*;public class Solution {public int findKth(int[] a, int n, int K) {return quickSort(a, 0, a.length - 1, K);}private int quickSort(int[] arr, int left, int right, int k){int p = partition(arr, left, right);// 改进后，很特殊的是，p是全局下标，只要p对上topK坐标就可以返回if (p == arr.length - k) {return arr[p];}else if (p < arr.length - k) {// 如果基准在左边，这在右边找return quickSort(arr, p + 1, right,k);}else {return quickSort(arr, left, p - 1,k);}}private int partition(int[] arr, int left, int right) {// 可优化成随机，或中位数int key = arr[left];while (left < right) {while (left < right && arr[right] >= key) right--;arr[left] = arr[right];while (left < right && arr[left] <= key) left++;arr[right] = arr[left];}arr[left] = key;return left;}
}