每天娃睡著之后洗漱完畢才有時間刷題宣肚，娃睡的晚昼钻，睡著要11點多状答，要刷題只能刷到凌晨2點，睡到床上大概2：30. 才持續(xù)一個星期多一點臉上就已經(jīng)開始長痘了咱揍。希望整個刷題過程不要太長颖榜，否則我后面要恢復會很艱難啊。
215.?Kth Largest Element in an Array
quicksort就是選出某一個數(shù)在數(shù)組里面應該待的位置煤裙。上一篇已經(jīng)提到了掩完。所以這里就可以用quick sort來找第n-k的位置上的數(shù)。n為數(shù)組長度硼砰。
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
