首页 > 代码库 > leetcode 215. Kth Largest Element in an Array 寻找第k个大的数---------- java
leetcode 215. Kth Largest Element in an Array 寻找第k个大的数---------- java
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.
寻找一个数组中第k大的数。
1、建立一个大小为k的数组,每次维护这个数组,属于暴力做法。
public class Solution { public int findKthLargest(int[] nums, int k) { int len = nums.length; int[] result = new int[k]; for (int i = 0; i < k ; i++){ result[i] = nums[i]; } for (int i = k; i < len; i++){ int min = result[0]; int pos = 0; for (int j = 1; j < k; j++){ if (min > result[j]){ min = result[j]; pos = j; } } if (nums[i] > min){ result[pos] = nums[i]; } } int ans = result[0]; for (int i = 1; i < k; i++){ System.out.println(result[i] + " " + result[0]); ans = Math.min(ans, result[i]); } return ans; } }
2、利用快排
public class Solution { public int findKthLargest(int[] nums, int k) { return QuickSort(nums, k, 0, nums.length - 1); } public int QuickSort(int[] nums, int k, int start, int end){ int left = start, right = end; int num = nums[start]; for (int i = end; i > start; i--){ if (nums[i] >= num){ swap(nums, end--, i); } } swap(nums, end, start); if (k == nums.length - end){ return nums[end]; } else if (k > nums.length - end){ return QuickSort(nums, k, left, end - 1); } else { return QuickSort(nums, k, end + 1, right); } } public void swap(int[] nums, int a, int b){ int num = nums[a]; nums[a] = nums[b]; nums[b] = num; } }
3、discuss中的快排。速度更快
public class Solution { public int findKthLargest(int[] nums, int k) { return select(nums, k-1); } // Quick select private int select(int[] nums, int k) { int left = 0, right = nums.length-1; while(true) { if(left == right) return nums[left]; int pivotIndex = medianOf3(nums, left, right); pivotIndex = partition(nums, left, right, pivotIndex); if(pivotIndex == k) return nums[k]; else if(pivotIndex > k) right = pivotIndex-1; else left = pivotIndex+1; } } //Use median-of-three strategy to choose pivot private int medianOf3(int[] nums, int left, int right) { int mid = left + (right - left) / 2; if(nums[right] > nums[left]) swap(nums, left, right); if(nums[right] > nums[mid]) swap(nums, right, mid); if(nums[mid] > nums[left]) swap(nums,left, mid); return mid; } private int partition(int[] nums, int left, int right, int pivotIndex) { int pivotValue =http://www.mamicode.com/ nums[pivotIndex]; swap(nums, pivotIndex, right); int index = left; for(int i = left; i < right; ++i) { if(nums[i] > pivotValue) { swap(nums, index, i); ++index; } } swap(nums, right, index); return index; } private void swap(int[] nums, int a, int b) { int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }
leetcode 215. Kth Largest Element in an Array 寻找第k个大的数---------- java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。