Leetcode Answers 215

继续刷题,这次是关于排序的问题,找出一个数列中第K大的数,可重复。

题目:
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.

思路:
作为一个用C#和.NET 4.6.2的人,我看到这道题的时候心里是平静甚至波澜不惊的,毕竟我有Linq啊,真是one liner解决的。。。所以我要换个思路,顺便换成Java来做,不然我会一心想用Linq的。。。先写下来one-liner的答案。

Answer:

1
2
3
4
5
public class Solution {
public int FindKthLargest(int[] nums, int k) {
return nums.OrderByDescending(c => c).Skip(k-1).First();
}
}

思路2:
那么k-th largest,摆明了是告诉我们要先sort。那我们就来看看quick sort之后取index,但是算的时候就会发现,我们有优化的空间,毕竟我们要的是k-th largest,那么当我们做partition的时候就要考虑分成k和len-k的两部分,然后答案就出来了。

Answer2:(这次是Java,也是和C#长得差不多)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
public int findKthLargest(int[] nums, int k) {
int start = 0, end = nums.length - 1, idx = nums.length - k;
while(start < end){
int pivot = partition(nums, start, end);
if (pivot < idx) start = pivot + 1;
else if(pivot > idx) end = pivot - 1;
else return nums[idx];
}
return nums[start];
}
private int partition(int[] nums, int start, int end) {
int pivot = nums[start], j = start+1;
for(int i=start+1;i<=end;i++){
if(nums[i]<pivot){
swap(nums, i, j);
j++;
}
}
j--;
swap(nums, start, j);
return j;
}
private void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}

考察:System.Linq果然是神器。。。Java要是也有Linq就好了,虽然已经有了Lambda expression,但是还是差点意思

以上。

17-04-25
@Sturbridge