05 August 2008
给定一个字符串数组 nums 和一个整数 k。 nums 中的每个字符串代表一个不带前导零的整数。
返回表示 nums 中第 k 个最大整数的字符串。
注意：重复的数字应该被清楚地计算。例如，如果 nums 是 [“1”,”2”,”2”]，则“2”是第一个最大整数，“2”是第二大整数，“1”是第三大整数。
PriorityQueue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public String kthLargestNumber(String[] nums, int k) {
PriorityQueue<String> pq = new PriorityQueue(new Comparator<String>(){
@Override
public int compare(String s1, String s2){
if(s1.length()==s2.length())
return s1.compareTo(s2);
else{
return Integer.compare(s1.length(), s2.length());
}
}
});
for(String num:nums){
pq.offer(num);
if(pq.size()>k){
pq.poll();
}
}
return pq.peek();
}
}
Quick Select
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
Random rand = new Random();
public String kthLargestNumber(String[] nums, int k) {
int len = nums.length;
k = len - k;
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = partition(nums, left, right + 1);
if (mid == k) {
return nums[mid];
} else if (mid < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return "";
}
private int partition(String[] nums, int left, int right) {
if (right - left == 1) {
return left;
}
int index = left + rand.nextInt(right - left);
String pivot = nums[index];
nums[index] = nums[left];
while (left < right) {
while (left < right && compare(nums[--right], pivot) >= 0) ;
if (left < right) {
nums[left] = nums[right];
}
while (left < right && compare(nums[++left], pivot) <= 0) ;
if (left < right) {
nums[right] = nums[left];
}
}
nums[left] = pivot;
return left;
}
public int compare(String a, String b) {
return a.length() == b.length() ? a.compareTo(b) : Integer.compare(a.length(), b.length());
}
}