有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
要求:时间复杂度 ,空间复杂度
数据范围:, ,数组中每个元素满足
有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
[1,3,5,2,2],5,3
2
[10,10,9,9,8,7,5,6,4,3,4,2],12,3
9
去重后的第3大是8,但本题要求包含重复的元素,不用去重,所以输出9
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; }
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; } }
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; } }
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]; } } }
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; } }
public int findKth(int[] a, int n, int K) { Arrays.sort(a); return a[n-K]; }
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; } }
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); } } }
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); } } }
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]; } }
import java.util.*; public class Solution { public int findKth(int[] a, int n, int K) { // write code here int target=n-K; //目标下标 int left=0; int right=n-1; while(left<=right){ int val=fun(a,left,right); if(val==target){ return a[val]; }else if(val>target){ right=val-1; }else{ left=val+1; } } return -1; } //快排思想 public int fun(int[] arr,int l,int r){ if(l>=r){ return l; } int povit=arr[l]; int left=l; int right=r; while(left<right){ while(left<right&&povit<=arr[right]){ right--; } while(left<right&&povit>=arr[left]){ left++; } swap(arr,left,right); } swap(arr,l,right); return left; } public void swap(int[] arr,int val1,int val2){ int temp=arr[val1]; arr[val1]=arr[val2]; arr[val2]=temp; } }
import java.util.*; public class Solution { public int findKth(int[] input, int n, int k) { // write code here ArrayList<Integer> list = new ArrayList<Integer>(); if(n == 0 || k == 0){ return -1; } //创建一个大小为K的小根堆 PriorityQueue<Integer> queuq = new PriorityQueue<>(k); //把数组的前k个元素放入到小根堆中 for(int i = 0; i < k; i++){ if(i >= n){ break; } queuq.add(input[i]); } for(int i = k; i < n; i++){ //如果当前元素大于堆顶元素,则弹出堆顶元素,放入当前元素 if(input[i] > queuq.peek()){ queuq.poll(); queuq.add(input[i]); } } return queuq.peek(); } }