Given an integer array, find the top k largest numbers in it.
Example
Given [3,10,1000,-99,4,100] and k = 3.
Return [1000, 100, 10].
解法一：
class Solution {
public:
/*
* @param nums: an integer array
* @param k: An integer
* @return: the top k largest numbers in array
*/
vector<int> topk(vector<int> nums, int k) {
std::priority_queue<int> heap;
for(int i = ; i < nums.size(); i++) {
heap.push(nums[i]);
}
std::vector<int> result;
for (int i = ; i < k; i++) {
result.push_back(heap.top());
heap.pop();
}
return result;
}
};
优先队列，类似于维护一个大小为k的最大堆/最小堆（STL中的priority_queue默认是最大堆），时间复杂度为O(n * logk)
解法二：
class Solution {
/*
* @param nums an integer array
* @param k an integer
* @return the top k largest numbers in array
*/
public int[] topk(int[] nums, int k) {
int[] temp = new int[k];
if(nums == null || nums.length == 0) {
return temp;
}
quickSort(nums, 0, nums.length - 1, k);
if(nums.length < k) {
return nums;
}
for(int i = 0; i < k; i++) {
temp[i] = nums[i];
}
return temp;
}
public void quickSort(int[] nums, int start, int end, int k) {
if (start >= end) {
return;
}
int left = start, right = end;
int mid = left + (right - left) / 2;
int pivot = nums[mid];
while(left <= right) {
while(left <= right && nums[left] > pivot) {
left++;
}
while(left <= right && nums[right] < pivot) {
right--;
}
if(left <= right) {
swap(nums, left, right);
left++;
right--;
}
}
quickSort(nums, start, right, k);
quickSort(nums, left, end, k);
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
};
快速排序，取出前k大的数，时间复杂度O(n*logn + k)