本文共 1970 字,大约阅读时间需要 6 分钟。
题目原文:
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. 题目大意: 寻找一个数组中第k大的数。 题目分析: (1) 朴素解法O(nlogn):排序,然后返回倒数第k个元素。 (2) Quick Select算法O(n): S1.选择一个中轴(可以使用快排中的三者取中法),比中轴大的数放到左边,比中轴小的数放到右边; S2.然后求出左边的长度l,若l==k,则中轴即为所求;若l>k,则从左边数组里面找第k大的数,若lpublic class Solution { public int findKthLargest(int[] nums, int k) { return select(nums, k-1); } 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 = 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; }}
成绩:
方法一:7ms,beats 74.67%,众数4ms,13.67% 方法二:2ms,beats 97.12% Cmershen的碎碎念: 这道题好像是一道很经典的题,似乎在《算法导论》中有对这道题大篇幅的详细描述。转载地址:http://lfomb.baihongyu.com/