首页 > 其他 > 详细

Kth Largest Element in an Array

时间:2015-05-23 18:23:51      阅读:258      评论:0      收藏:0      [点我收藏+]

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array‘s length.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

算法:

最小堆排序

public class Solution {
    public int findKthLargest(int[] nums, int k) {
		int[] b = new int[k];
		for (int i = 0; i < k; i++) {
			b[i] = nums[i];
		}
		for(int i=b.length/2;i>=0;i--){
			minHeapSort(b,i,b.length);
		}
		for (int i = k; i < nums.length; i++) {
			if (nums[i] > b[0]) {
				b[0] = nums[i];
				minHeapSort(b,0,b.length);
			}
		}
		return b[0];
	}

	private void minHeapSort(int[] b,int i, int n) {
		int tmp = b[i];
		int child;
		for (; i * 2 + 1 < n; i = child) {
			child = i * 2 + 1;
			if (child < n - 1 && b[child + 1] < b[child]) {
				child++;
			}
			if (tmp > b[child]) {
				b[i] = b[child];
			} else
				break;
		}
		b[i] = tmp;
	}
}


Kth Largest Element in an Array

原文:http://blog.csdn.net/u010786672/article/details/45936211

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!