有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
要求：时间复杂度 )
，空间复杂度 )
数据范围：
， 
，数组中每个元素满足 
[编程题]寻找第K大
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*/
public int findKth (int[] a, int n, int K) {
// write code here
// 快速排序 划分的思想
int i = 0, j = n - 1, k;
while (true) {
k = partition(a, i, j);
if (k == K - 1) return a[k];
else if (k < K - 1) i = k + 1;
else j = k - 1;
}
// qsort(a, 0, n - 1); // 验证快排成功
// return a[K - 1];
}
// 快排
public void qsort(int[] a, int i, int j) {
if (i >= j) return;
int k = partition(a, i, j);
qsort(a, i, k - 1);
qsort(a, k + 1, j);
}
// 快排的一次划分 [确定一个数的最终位置]
public int partition(int[] a, int i, int j) { // i大 --- 小j
int k = i;
while (i <= j) {
while (i <= j && a[i] >= a[k]) i++; // 都带=
while (i <= j && a[j] <= a[k]) j--;
if (i <= j) {
a[i] ^= a[j] ^ (a[j] = a[i]); // 交换a[i] a[j]
}
}
a[j] ^= a[k] ^ (a[k] = a[j]); // 交换a[j] a[k]枢轴
return j; // i不行
}
}
发表于 2025-02-08 18:26:10
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型一维数组
* @param n int整型
* @param K int整型
* @return int整型
*/
public int findKth (int[] a, int n, int K) {
// write code here
// 1.先进行排序 - O(NlogN)
// 手写快排
// Arrays.sort(a);
quickSort(a);
// 2.直接取出第K大元素返回
return a[n - K];
}
// 快速排序主方法
public void quickSort(int[] a) {
if (a.length == 0 || a.length == 1) {
return;
}
process(a, 0, a.length - 1);
}
// 快速排序递归方法
public void process(int[] a, int l, int r) {
// 递归出口
if (l >= r) {
return;
}
// 先分区，再根据pivort的位置左右递归
int[] i = partition(a, l, r);
process(a, l, i[0]);
process(a, i[1], r);
}
// 快速排序分区方法
public int[] partition (int[] a, int l, int r) {
int p = a[l];
int smaller = l - 1;
int larger = r + 1;
int i = l;
while (i < larger) {
if (a[i] == p) {
// 当前值等于p，则直接掠过
i++;
} else if (a[i] < p) {
// 发现当前值比p更小，则与smaller的下一个位置交换，smaller自增，表示小于区右扩一位
// 同时i可以自增，因为从前面交换过来的元素要么等于p，要么是自己交换自己，无需再次比较
int t = a[i];
a[i] = a[smaller + 1];
a[smaller + 1] = t;
smaller++;
i++;
} else {
// 发现当前值比p更大，则与larger的前一个位置交换，larger自减，表示大于区左扩一位
// 此时i不能自增，因为从后面交换过来的元素不知道其与p的大小关系，需要再次比较
int t = a[i];
a[i] = a[larger - 1];
a[larger - 1] = t;
larger--;
}
}
int[] result = {smaller, larger};
return result;
}
}
发表于 2024-09-02 17:27:19
回复(0)
import java.util.*;
public class Solution {
public int findKth (int[] a, int n, int K) {
int[] nums = new int[10000001];
int max = 0;
int index = 0;
int count = 0;
for(int num: a) {
nums[num] += 1;
max = num > max? num: max;
}
for(index = max; index >= 0; index --) {
count += nums[index];
if(count >= K) break;
}
return index;
}
}
时间复杂度为2n的方法，nums的大小取决于a中值的限值范围
发表于 2024-07-18 00:11:00
回复(1)
public int findKth (int[] a, int n, int K) {
// write code here
int[] heap = new int[K];
for (int i = 0; i < n; i++) {
if (i < K) {
heap[i]= a[i];
heapInsert(heap, i);
} else {
if (a[i] <= heap[0]) {
continue;
}
heap[0] = a[i];
adjust(heap);
}
}
return heap[0];
}
private static void heapInsert(int[] arr, int index) {
while (arr[index] < arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private static void adjust(int[] heep) {
int index = 0;
int left = 2 * index + 1;
while (left < heep.length) {
int smaller = left + 1 < heep.length && heep[left + 1] < heep[left] ? left + 1 : left;
int minimum = heep[index] < heep[smaller] ? index : smaller;
if (minimum == index) {
break;
}
swap(heep, index, minimum);
index = minimum;
left = 2 * index + 1;
}
}
private static void swap(int[] heep, int a, int b) {
int temp = heep[a];
heep[a] = heep[b];
heep[b] = temp;
}
编辑于 2024-01-31 21:05:12
回复(0)
public class Solution {
/**
* 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
*
*
* @param a int整型一维数组
* @param n int整型
* @param k int整型
* @return int整型
*/
public int findKth (int[] a, int n, int k) {
if (n < k || k == 0) {
return -1;
}
quickSort(a, 0, n - 1);
return a[n - k];
}
public void quickSort(int[] a, int start, int end) {
int low = start;
int high = end;
int reference = a[start];
if (low >= high) {
return;
}
while (low < high) {
while (a[low] <= reference && low < end) {
low++;
}
while (a[high] >= reference && high > start) {
high--;
}
if (low < high) {
swap(a, low, high);
}
}
swap(a, start, high);
quickSort(a, start, high - 1);
quickSort(a, high + 1, end);
}
public void swap(int[] a, int low, int high) {
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
}
发表于 2023-10-30 16:01:18
回复(0)
一直看到这道题就没做，正巧面试问到了这道题，差点没做出来，后悔，于是今天来尝试做一下。
这道题虽然限制了空间复杂度为O（1），但是在验证代码的时候好像并没有关注这个，所以我的答案可能不符合题目要求
import java.util.*;
public class Solution {
private class Node {
public int val;
public Node next = null;
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型一维数组
* @param n int整型
* @param K int整型
* @return int整型
*/
public int findKth (int[] a, int n, int k) {
// write code here
Node head = new Node();
Node now = head;
Node next;
int i = 1;
head.val = a[0];
// 构建最小堆，这里构建的是一个有序的链表，方便移动head
for (; i < k; i++) {
Node aaa = new Node();
aaa.val = a[i];
if (a[i] >= head.val) {
now = head;
next = now.next;
while (next != null) {
if (a[i] <= next.val) {
break;
}
now = next;
next = next.next;
}
now.next = aaa;
aaa.next = next;
} else {
aaa.next = head;
head = aaa;
}
}
// 和head比较：如果比head小就不用管，如果比head大，就看看是插入最小堆中哪里。注意如果插入，head需要往后移
for (; i < n; i++) {
Node aaa = new Node();
aaa.val = a[i];
if (a[i] > head.val) {
now = head;
next = now.next;
while (next != null) {
if (a[i] <= next.val) {
break;
}
now = next;
next = next.next;
}
now.next = aaa;
aaa.next = next;
head = head.next;
}
}
return head.val;
}
}
发表于 2023-09-15 09:42:35
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型一维数组
* @param n int整型
* @param K int整型
* @return int整型
*/
public int findKth (int[] a, int n, int K) {
// write code here
return QuickSort(a, 0, n - 1, K);
}
public int QuickSort(int[] a, int low, int high, int K) {
int i = low;
int j = high;
int temp = a[i];
while (i < j) {
while (i < j && a[j] <= temp) j--;
a[i] = a[j];
while (i < j && a[i] >= temp)i++;
a[j] = a[i];
}
a[i] = temp;
if (i + 1 < K) {
return QuickSort(a, i + 1, high, K);
} else if (i + 1 > K) {
return QuickSort(a, low, i - 1, K);
} else {
return a[i];
}
}
}
发表于 2023-08-12 22:39:43
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型一维数组
* @param n int整型
* @param K int整型
* @return int整型
*/
public int findKth (int[] a, int n, int K) {
// write code here
Arrays.sort(a);
int index = n - K;
return a[index];
}
}
发表于 2023-07-06 19:35:42
回复(0)
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
shuffle(a,n);
int l=0;
int r=n-1;
K=n-K;
while(l<=r){
int p=partition(a,l,r);
if(p<K){ //p太小了
l=p+1;
}else if(p>K){
r=p-1;
}else{
return a[p];
}
}
return -1;
}
public void shuffle(int[] a,int n){
Random rand=new Random();
for(int i=0;i<n;i++){
int r=i+rand.nextInt(n-i);
swap(a,i,r);
}
}
public void swap(int[] a,int i,int j){
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
public int partition(int[] a,int l,int r){
int i=l;
int j=r;
int ppp=a[l];
while(i<j){
while(i<r&&a[i]<=ppp){
i++;
}
while(j>l&&a[j]>=ppp){
j--;
}
if(i>=j){ //注意这里的break
break;
}
swap(a,i,j);
}
swap(a,j,l);//为啥是j和l
return j;
}
}
发表于 2023-05-20 22:10:50
回复(0)
public int findKth(int[] a, int n, int K) {
Arrays.sort(a);
return a[n-K];
}
发表于 2023-02-08 21:25:07
回复(2)
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
sort(a,0,n-1);
return a[n-K];
}
private void sort(int[] a,int l,int r){
if(l>=r){
return;
}
int[] p = patition(a,l,r);
sort(a,0,p[0]-1);
sort(a,p[1]+1,r);
}
private int[] patition(int[] a,int l,int r){
if(l>r){
return new int[]{-1,-1};
}
if(l==r){
return new int[]{l,r};
}
int less = l-1;
int index = l;
int more = r;
while(index<more){
if(a[index]==a[r]){
index++;
} else if(a[index]<a[r]){
swap(a,index++,++less);
} else if(a[index]>a[r]){
swap(a,index,--more);
}
}
swap(a,more,r);
return new int[]{less+1,more};
}
private void swap(int[] a,int i,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
sort(a,0,n-1);
return a[n-K];
}
private void sort(int[] a,int l,int r){
if(l>=r){
return;
}
int[] p = patition(a,l,r);
sort(a,0,p[0]-1);
sort(a,p[1]+1,r);
}
private int[] patition(int[] a,int l,int r){
if(l>r){
return new int[]{-1,-1};
}
if(l==r){
return new int[]{l,r};
}
int less = l-1;
int index = l;
int more = r;
while(index<more){
if(a[index]==a[r]){
index++;
} else if(a[index]<a[r]){
swap(a,index++,++less);
} else if(a[index]>a[r]){
swap(a,index,--more);
}
}
swap(a,more,r);
return new int[]{less+1,more};
}
private void swap(int[] a,int i,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
发表于 2022-12-10 20:59:25
回复(0)
一种堆排序，一种归并排序
public class Solution {
public int findKth(int[] a, int n, int K) {
// 归并排序
//merge(a, 0, n - 1);
//return a[K - 1];
// 堆排序
return heapSort(a, n, K);
}
public void merge(int [] input, int left, int right){
if(left >= right) return;
int mid = left + (right - left) / 2;
merge(input, left, mid);
merge(input, mid + 1, right);
int[] tempArr = new int[input.length];
int temL = left,tempR = mid + 1,tempArrIndex = 0;
while (temL <= mid && tempR <= right){
if(input[temL] <= input[tempR]){
tempArr[tempArrIndex] = input[tempR];
tempR++;
}else{
tempArr[tempArrIndex] = input[temL];
temL++;
}
tempArrIndex++;
}
while (temL <= mid){
tempArr[tempArrIndex] = input[temL];
temL++;
tempArrIndex++;
}
while (tempR <= right){
tempArr[tempArrIndex] = input[tempR];
tempR++;
tempArrIndex++;
}
tempArrIndex = 0;
for (int i = left; i <= right; i++) {
input[i] = tempArr[tempArrIndex];
tempArrIndex++;
}
}
public int heapSort(int[] arr, int n, int K){
for(int i = n / 2 - 1; i >= 0; i--) build(arr, i, n);
int temp;
for(int i = n - 1; i >= n - K; i--){
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
build(arr, 0, i);
}
return arr[n-K];
}
public void build(int [] arr, int i, int len){
int temp = arr[i];
for(int k = i * 2 +1; k < len; k = k * 2 + 1){
if(k + 1 < len && arr[k] < arr[k+1]){
k++;
}
if(arr[k] > temp){
arr[i] = arr[k];
i = k;
}
}
arr[i] = temp;
}
}
发表于 2022-11-12 11:20:05
回复(0)
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
quickSort(a,0,n-1);
return a[n-K];
}
public void quickSort(int[] arr,int left,int right){
int midIndex=(left+right)/2;
int midVal=arr[midIndex];
int l=left;
int r=right;
int temp;
while(l<r){
while(arr[l]<midVal){
l++;
}
while(arr[r]>midVal){
r--;
}
if(l>=r){
break;
}
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
if(arr[l]==midVal){
r--;
}
if(arr[r]==midVal){
l++;
}
}
if(l==r){
l++;
r--;
}
if(left<r){
quickSort(arr,left,r);
}
if(l<right){
quickSort(arr,l,right);
}
}
}
发表于 2022-10-30 16:53:57
回复(0)
//JAVA...
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
Arrays.sort(a);
return a[n-K];
}
}
发表于 2022-10-20 12:07:15
回复(0)
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
quickSort(a,0,n-1,n,K);
return a[n-K];
}
public void quickSort(int[] a,int left,int right,int n,int K){
if(left>=right)return;
int ref=a[left];
int l=left,r=right;
while(l<r){
while(a[r]>=ref&&l<r){
r--;
}
if(l<r){
a[l++]=a[r];
}
while(a[l]<=ref&&l<r){
l++;
}
if(l<r){
a[r--]=a[l];
}
}
a[l]=ref;
if(l==n-K){
return;
}else if(l>n-K){
quickSort(a,left,l-1,n,K);
}else{
quickSort(a,l+1,right,n,K);
}
}
}
发表于 2022-09-06 09:36:43
回复(0)
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
Arrays.sort(a);
return a[n-K];
}
}
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
Arrays.sort(a);
return a[n-K];
}
}
发表于 2022-09-01 11:14:33
回复(0)
public int findKth(int[] a, int n, int K) {
// write code here
int leftIndex = 0;
int rightIndex = n-1;
return find(a,n,K,leftIndex,rightIndex);
}
private int find(int[] a, int n, int K,int leftIndex,int rightIndex) {
int initLeftIndex = leftIndex;
int initRightIndex = rightIndex;
int randomIndex = new Random().nextInt(n);
//随机一个与最后值做交换，来打破最差的情况的可能性
int target = a[randomIndex + initLeftIndex];
a[randomIndex + initLeftIndex] = a[rightIndex];
a[rightIndex] = target;
for(int i = initLeftIndex;i<=initRightIndex;) {
if(i>rightIndex) {
break;
}
int current = a[i];
if(current < target) {
a[i] = a[leftIndex];
a[leftIndex] = current;
leftIndex ++;
if(leftIndex>=rightIndex) {
break;
}
i++;
} else if(current > target) {
a[i] = a[rightIndex];
a[rightIndex] = current;
rightIndex --;
if(leftIndex>=rightIndex) {
break;
}
} else {
i++;
}
}
int findIndex = initLeftIndex + n - K;
if(leftIndex > findIndex) {
//向小于区域查找
return find(a,leftIndex-initLeftIndex,K-(initLeftIndex + n - leftIndex),initLeftIndex,leftIndex-1);
} else if(rightIndex < findIndex) {
//向大于区域查找
return find(a,initRightIndex - rightIndex,K,rightIndex+1,initRightIndex);
} else {
return a[leftIndex];
}
}
发表于 2022-08-30 19:17:31
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-13 16:01:06
-
2023-02-26 18:08:27
-
2023-02-21 15:33:43
-
2023-02-19 21:18:16
-
2023-02-02 14:25:44
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
