排序
215.数组中的第k个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
1
2
| 输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
|
示例 2:
1
2
| 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
|
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
leetcode原题地址
解法
- 是用堆排序
1
2
3
4
5
6
7
8
9
10
11
12
| public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq=new PriorityQueue<>();
for (int num : nums) {
pq.add(num);
if(pq.size()>k){
pq.poll();
}
}
return pq.poll();
}
|
时间复杂度O(NlogK)，空间复杂度为O(K)
- 使用快排
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
| public int findKthLargest(int[] nums, int k) {
sort(nums);
return nums[k-1];
}
private void sort(int[] arr){
doSort(arr,0,arr.length-1);
}
private void doSort(int[] arr,int left,int right){
if(left<right){
int pivot = partition(arr, left, right);
doSort(arr,left,pivot-1);
doSort(arr,pivot,right);
}
}
private int partition(int[] arr,int left,int right){
int mid=(left+right)/2;
int pivot=arr[mid];
while (left<=right){
while (right>=0&&arr[right]<pivot){
right--;
}
while (left<arr.length&&arr[left]>pivot){
left++;
}
if(left<=right){
swap(arr, left, right);
left++;
right--;
}
}
return left;
}
private void swap(int[] arr,int a,int b){
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
|
- 快速选择
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
| public int findKthLargest(int[] nums, int k) {
int l=0;
int r=nums.length-1;
k=nums.length-k;
while (l<r){
int p = partition(nums, l, r);
if(p==k){
break;
}else if(p>k){
r=p-1;
}else {
l=p+1;
}
}
return nums[k];
}
private int partition(int[] a, int l, int h) {
int i = l, j = h + 1;
while (true) {
while (a[++i] < a[l] && i < h) {};
while (a[--j] > a[l] && j > l) {};
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, l, j);
return j;
}
private void swap(int[] arr,int a,int b){
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
|
347. 前k个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
1
2
| 输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
|
示例 2:
1
2
| 输入: nums = [1], k = 1
输出: [1]
|
说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
leetcode原题地址
解法
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
| public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> count = new HashMap();
for (int n: nums) {
count.put(n, count.getOrDefault(n, 0) + 1);
}
PriorityQueue<Integer> heap =
new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2));
for (int n: count.keySet()) {
heap.add(n);
if (heap.size() > k){
heap.poll();
}
}
List<Integer> top_k = new LinkedList();
while (!heap.isEmpty()) {
top_k.add(heap.poll());
}
Collections.reverse(top_k);
return top_k;
}
|
75. 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
1
2
| 输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
|
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
leetcode原题地址
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public void sortColors(int[] nums) {
int zero = -1, one = 0, two = nums.length;
while (one < two) {
if (nums[one] == 0) {
swap(nums, ++zero, one++);
} else if (nums[one] == 2) {
swap(nums, --two, one);
} else {
++one;
}
}
}
private void swap(int[] arr,int a,int b){
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
|