题目链接:LeetCode215展开目录
题解展开目录
第一种做法,直接排序完了取,时间复杂度 O (logn)
- class Solution {
- public int findKthLargest(int[] nums, int k) {
- Arrays.sort(nums);
- return nums[nums.length - k];
- }
- }
第二种做法,BFPRT 算法,时间复杂度 O (n)
- class Solution {
- public static int getMinKthByBFPRT(int[] arr,int k) {
- int[] copyArr = new int[arr.length];
- copyArr = copyArray(arr);
- return bfprt(copyArr,0,copyArr.length - 1,k - 1);
- }
- public static int[] copyArray(int[] arr) {
- int[] tmp = new int[arr.length];
- for(int i = 0;i != arr.length;i++)
- tmp[i] = arr[i];
- return tmp;
- }
- public static int bfprt(int[] arr,int begin,int end,int i) {//begin到end范围内求第i小的数
- if(begin == end)
- return arr[begin];
- int pivot = medianOfMedians(arr,begin,end);//中位数作为划分值
- int[] pivotRange = partition(arr,begin,end,pivot);//进行划分,返回等于区域
- if(i >= pivotRange[0] && i <= pivotRange[1])
- return arr[i];
- else if(i < pivotRange[0])
- return bfprt(arr,begin,pivotRange[0] - 1,i);
- else
- return bfprt(arr,pivotRange[1] + 1,end,i);
- }
-
- public static int medianOfMedians(int[] arr,int begin,int end) {
- int num = end - begin + 1;
- int offset = num % 5 == 0 ? 0 : 1;
- int[] mArr = new int[num / 5 + offset];
- for(int i = 0; i < mArr.length;i++) {
- int beginI = begin + i * 5;
- int endI = beginI + 4;
- mArr[i] = getMedian(arr,beginI,Math.min(end,endI));
- }
- return bfprt(mArr,0,mArr.length - 1,mArr.length / 2);
- }
-
- public static int getMedian(int[] arr,int begin,int end) {
- Arrays.sort(arr,begin,end);
- int sum = end + begin;
- int mid = (sum / 2) + (sum % 2);
- return arr[mid];
- }
-
- public static void insertSort(int[] arr,int begin,int end) {
- for(int i = begin + 1;i != end + 1;i++) {
- for(int j = i;j != begin;j--) {
- if(arr[j - 1] > arr[j])
- swap(arr,j - 1,j);
- else
- break;
- }
- }
- }
- public static int[] partition(int[] arr,int begin,int end,int pivotValue) {
- int small = begin - 1;
- int cur = begin;
- int big = end + 1;
- while(cur != big) {
- if(arr[cur] < pivotValue)
- swap(arr,++small,cur++);
- else if(arr[cur] > pivotValue)
- swap(arr,cur,--big);
- else
- cur++;
- }
- int[] range = new int[2];
- range[0] = small + 1;
- range[1] = big - 1;
- return range;
- }
-
- public static void swap(int[] arr,int i,int j) {
- int t = arr[i];
- arr[i] = arr[j];
- arr[j] = t;
- }
- public int findKthLargest(int[] nums, int k) {
- return getMinKthByBFPRT(nums,nums.length - k + 1);
- }
- }