136.Kth Largest Element in an Array

Subscribe to see which companies asked this question

求一个数组中第k大的元素。

方法一：选用小顶堆，topk的思想做。

方法二：选用快排做，每次划分返回划分的下标，然后判断继续划分是左边数组还是右边数组。

	int heap_size = 0;// 表示堆中有多少个元素/*** 返回数组中第k大元素(输入的k值合法)。* 采用小顶堆的思想，维护一个有k个元素的小顶堆。然后遍历后面的元素，如果比堆顶大则将堆顶置为该元素，否则不变。* topk的思想。* @param nums* @param k* @return*/public int findKthLargest(int[] nums, int k) {int[] heapArr = new int[k];heapArr = Arrays.copyOfRange(nums, 0, k);build_Min_Heap(heapArr);int len = nums.length;for(int i=k;i<len;i++){if(nums[i]>heapArr[0]){heapArr[0] = nums[i];min_Heapify(heapArr, 0);}}return  heapArr[0];}public void build_Min_Heap(int[] A) {// 给一个数据结构为Element的数组把它建成大顶堆  运行时间复杂度是 O(n)heap_size = A.length;for (int i = (heap_size - 1) / 2; i >= 0; i--) {min_Heapify(A, i);}}public void min_Heapify(int A[], int i) { // 维护最小堆的性质 时间复杂度是 lgn  维护以i为根节点的堆的最小堆的性质int l = i * 2 + 1;int r = (i + 1) * 2;int smallest = i;if (l < heap_size && A[l] < A[i]) {smallest = l;}if (r < heap_size && A[r] < A[smallest]) {smallest = r;}if (i != smallest) {   int temp;temp = A[smallest];A[smallest] = A[i];A[i] = temp;min_Heapify(A, smallest);}}

/*** 返回数组中第k大元素(输入的k值合法)。* 采用快排的思想,每次进行划分之后根据返回的下标确定下一步是要对左边数组进行划分还是右边数组进行划分。* @param nums* @param k* @return*/public int findKthLargest(int[] nums, int k) {int len = nums.length;int start = 0;int end = len-1;int index = partition(nums,start,end);while(index != k-1){if(index>k-1){end = index - 1;}else{start = index + 1;}index = partition(nums,start,end);}return nums[k-1];}/***  对数组input[start,end]中的元素进行划分。*  选择input[end]为枢纽元素privot,大于等于privot的放在左边，小于privot的放在右边。*  返回的是枢纽元素的下标。*/int partition(int [] input,int start,int end){int i = start-1;int j = start;int privot = input[end];int temp;for(;j<end;j++){if(input[j]>=privot){i++;temp = input[j];input[j] = input[i];input[i] = temp;}}i++;temp = input[i];input[i] = privot;input[end] = temp;return i;}