每天娃睡着之后洗漱完毕才有时间刷题，娃睡的晚，睡着要11点多，要刷题只能刷到凌晨2点，睡到床上大概2：30. 才持续一个星期多一点脸上就已经开始长痘了。希望整个刷题过程不要太长，否则我后面要恢复会很艰难啊。
215. Kth Largest Element in an Array
quicksort就是选出某一个数在数组里面应该待的位置。上一篇已经提到了。所以这里就可以用quick sort来找第n-k的位置上的数。n为数组长度。
my solution:
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length == 1) return nums[0];
int kth = nums.length - k;
int left = 0, right = nums.length -1;
while(left < right) {
int mid = partition(nums, left, right);
if(mid == kth) {
return nums[mid];
} else if(mid<kth) {
left = mid + 1;
} else {
right = mid -1;
}
}
return nums[left];
}
private void swap(int[] arr, int value1, int value2) {
int temp = arr[value1];
arr[value1] = arr[value2];
arr[value2] = temp;
}
private int partition(int[] arr, int low, int high) {
int p = low;
int j = low+1;
while(j<=high) {
if(arr[j]<arr[low]){
swap(arr, ++p, j);
}
j++;
}
swap(arr, low, p);
return p;
}
}
time complexity : O(n) in average, O(n*n) in the worst case.
space complexity: O(1)
347. Top K Frequent Elements 类似
quicksort time complexity worst case O(n*n), when array is sorted and pivot is start or end
网友评论