Skip to content

Commit 94c07ef

Browse files
linwtlinwt
committed
215.数组中的第K个最大元素，排序算法
1 parent 451a781 commit 94c07ef

File tree

4 files changed

+273
-16
lines changed

4 files changed

+273
-16
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,6 +56,7 @@
5656
200. 岛屿数量
5757
203. 移除链表元素
5858
206. 反转链表
59+
215. 数组中的第K个最大元素
5960
216. 组合总和 III
6061
226. 翻转二叉树
6162
234. 回文链表

‎leetcode_Java/Solution0215.java

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
// 215. 数组中的第K个最大元素
2+
3+
4+
/*
5+
排序后取倒数第k个元素，api使用快速排序
6+
*/
7+
class Solution {
8+
public int findKthLargest(int[] nums, int k) {
9+
Arrays.sort(nums);
10+
return nums[nums.length - k];
11+
}
12+
}
13+
14+
15+
// 具体见“十大排序算法_Java”
16+
17+
/*
18+
快速排序：
19+
1、一次排序操作将返回一个已经排好位置的中点索引mid，该索引左边的元素都小于它，右边的元素都大于等于它
20+
2、找第K个最大元素不用整个数组都排序，将中点索引mid与目标索引target比较，直接返回结果 或 选择递归左或右半部分继续排序
21+
3、递归方法：
22+
1）方法功能：根据数组、指定左右边界、目标值，进行一次排序，获取排序后的中点索引与目标索引比较，相等则返回目标值
23+
2）终止条件：左边界等于右边界，说明只剩一个元素，不用排序，直接返回该元素
24+
由于k在数组长度范围内，目标值一定存在，每次选择有效区间，mid每次加减1，所以不存在左边界大于右边界的情况
25+
3）递归逻辑：未找到目标值之前，排序好的中点的左半部分或右半部分数组也需要同样的操作寻找目标值，调用同样的方法进行排序，并接收递归方法返回值，最后返回结果
26+
*/
27+
class Solution {
28+
public int findKthLargest(int[] nums, int k) {
29+
int n = nums.length;
30+
return mainSort(nums, 0, n - 1, n - k);
31+
}
32+
33+
// 递归方法
34+
private int mainSort(int[] nums, int left, int right, int target) {
35+
if (left == right) {
36+
return nums[left];
37+
}
38+
int res;
39+
int mid = partition(nums, left, right);
40+
if (mid == target) {
41+
res = nums[target];
42+
} else if (mid > target) {
43+
res = mainSort(nums, left, mid - 1, target);
44+
} else {
45+
res = mainSort(nums, mid + 1, right, target);
46+
}
47+
return res;
48+
}
49+
50+
// 一次排序操作
51+
private int partition(int[] nums, int left, int right) {
52+
int index = left + 1;
53+
for (int i = index; i <= right; i++) {
54+
if (nums[i] < nums[left]) {
55+
swap(nums, i, index);
56+
index++;
57+
}
58+
}
59+
swap(nums, left, index - 1);
60+
return index - 1;
61+
}
62+
63+
// 交换元素
64+
private void swap(int[] nums, int x, int y) {
65+
int temp = nums[x];
66+
nums[x] = nums[y];
67+
nums[y] = temp;
68+
}
69+
}
70+
71+
72+
/*
73+
最大堆排序：
74+
1、先将普通数组调整成最大堆数组
75+
2、堆顶元素就是最大值，将堆顶元素交换到数组尾部，重新调整剩余数组元素为最大堆
76+
3、循环处理第2步，最终数组升序排序
77+
4、找第K个最大元素不用整个数组都排序，每次调整都会将剩余数组最大值交换到数组尾部，记录交换次数，直到第K个最大元素时直接返回结果
78+
*/
79+
class Solution {
80+
public int findKthLargest(int[] nums, int k) {
81+
int n = nums.length;
82+
for (int i = n / 2 - 1; i >= 0; i--) {
83+
maxHeapify(nums, i, n);
84+
}
85+
while (n > 0 && k > 0) {
86+
swap(nums, 0, n - 1);
87+
n--;
88+
k--;
89+
maxHeapify(nums, 0, n);
90+
}
91+
return nums[n];
92+
}
93+
94+
private void maxHeapify(int[] nums, int root, int n) {
95+
int maxIndex = root;
96+
int left = root * 2 + 1, right = root * 2 + 2;
97+
if (left < n && nums[left] > nums[maxIndex])
98+
maxIndex = left;
99+
if (right < n && nums[right] > nums[maxIndex])
100+
maxIndex = right;
101+
if (maxIndex != root) {
102+
swap(nums, maxIndex, root);
103+
maxHeapify(nums, maxIndex, n);
104+
}
105+
}
106+
107+
private void swap(int[] nums, int x, int y) {
108+
int temp = nums[x];
109+
nums[x] = nums[y];
110+
nums[y] = temp;
111+
}
112+
}

‎十大排序算法_Java/Heap.java

Lines changed: 118 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,52 @@
11
package sort;
22

3+
/*
4+
1、堆：堆本质上就是一棵完全二叉树，它的每一个节点都必须大于或者小于其子节点
5+
2、最大堆：每个节点都大于或者等于子树所有节点的堆称为最大堆
6+
最小堆：每个节点都小于或者等于子树所有节点的堆称为最小堆
7+
3、数组存储堆，节点的索引关系如下
8+
索引角度：起始索引为0，某个节点在数组中的索引为i，则其（直接看索引，好记）
9+
1）父节点索引：(i-1)/2
10+
2）左子节点索引：2i+1
11+
3）右子节点索引：2i+2
12+
位置角度：起始位置为1，某个节点在数组中的位置为j，则其（换算了一遍，不好记）
13+
1）父节点索引：((j-1)-1)/2 = j/2-1
14+
2）左子节点索引：2(j-1)+1 = 2j-1
15+
3）右子节点索引：2(j-1)+2 = 2j
16+
*/
17+
18+
319
// 堆排序
20+
/*
21+
最大堆排序思路：
22+
1、先将普通数组调整成最大堆数组
23+
2、堆顶元素就是最大值，将堆顶元素交换到数组尾部，重新调整剩余数组元素为最大堆
24+
3、循环处理第2步，最终数组升序排序
25+
*/
426
public class Heap {
527
private int n;
628

729
public int[] heapSort(int[] nums) {
830
n = nums.length;
9-
// 堆的构造需要跟子节点比较，所以从最后一个非叶子结点开始向上构造最大堆
10-
for (int i = n / 2 - 1; i >= 0; i--)
11-
max_heapify(nums, i);
31+
// 堆的构造需要跟子节点比较，所以从 最后一个非叶子结点(最后一个节点的父节点) 开始向上构造最大堆
32+
// 必须从下往上逐层调整，每一层小值向下浮动，大值交换上去，最终最大值会升到根节点
33+
for (int i = n / 2 - 1; i >= 0; i--) {
34+
maxHeapify(nums, i);
35+
}
36+
// 在最大堆的基础上，只改变了一个元素，重新调整为最大堆只需进行一次小值向下浮动即可
1237
while (n > 0) {
13-
// 根节点与最后一个节点交换
38+
// 根节点与最后一个节点交换，最终形成升序排序
1439
swap(nums, 0, n - 1);
40+
// n控制着剩余可调整的数组元素范围，即堆顶元素交换到数组尾部后就不参与堆调整了
1541
n--;
16-
// 交换完调整最大堆，父子两两交换，把小值往下换，把最大值升到根节点
17-
max_heapify(nums, 0);
42+
// 交换完重新调整成最大堆，父子两两交换，把小值往下换，把最大值升到根节点
43+
maxHeapify(nums, 0);
1844
}
1945
return nums;
2046
}
2147

22-
// 堆调整的逻辑：父节点与子节点较大者交换，最终最大值会升到根节点
23-
private void max_heapify(int[] nums, int root) {
48+
// 方法作用：将小值向下浮动。即父节点与子节点较大者交换，并递归处理
49+
private void maxHeapify(int[] nums, int root) {
2450
int maxIndex = root;
2551
// 索引从0开始
2652
int left = root * 2 + 1, right = root * 2 + 2;
@@ -30,10 +56,10 @@ private void max_heapify(int[] nums, int root) {
3056
// 如果有右孩子，且右孩子大于父节点和左孩子，则将最大指针指向右孩子
3157
if (right < n && nums[right] > nums[maxIndex])
3258
maxIndex = right;
33-
// 如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
59+
// 如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置
3460
if (maxIndex != root) {
3561
swap(nums, maxIndex, root);
36-
max_heapify(nums, maxIndex);
62+
maxHeapify(nums, maxIndex);
3763
}
3864
}
3965

@@ -51,3 +77,85 @@ public static void main(String[] args) {
5177
System.out.println(num);
5278
}
5379
}
80+
81+
82+
// 最大堆，升序排序，去注释
83+
public class Heap {
84+
private int n;
85+
86+
public int[] heapSort(int[] nums) {
87+
n = nums.length;
88+
for (int i = n / 2 - 1; i >= 0; i--) {
89+
maxHeapify(nums, i);
90+
}
91+
while (n > 0) {
92+
swap(nums, 0, n - 1);
93+
n--;
94+
maxHeapify(nums, 0);
95+
}
96+
return nums;
97+
}
98+
99+
private void maxHeapify(int[] nums, int root) {
100+
int maxIndex = root;
101+
int left = root * 2 + 1, right = root * 2 + 2;
102+
if (left < n && nums[left] > nums[maxIndex])
103+
maxIndex = left;
104+
if (right < n && nums[right] > nums[maxIndex])
105+
maxIndex = right;
106+
if (maxIndex != root) {
107+
swap(nums, maxIndex, root);
108+
maxHeapify(nums, maxIndex);
109+
}
110+
}
111+
112+
private void swap(int[] nums, int x, int y) {
113+
int temp = nums[x];
114+
nums[x] = nums[y];
115+
nums[y] = temp;
116+
}
117+
}
118+
119+
120+
/*
121+
最小堆排序思路：
122+
1、先将普通数组调整成最小堆数组
123+
2、堆顶元素就是最小值，将堆顶元素交换到数组尾部，重新调整剩余数组元素为最小堆
124+
3、循环处理第2步，最终数组降序排序
125+
*/
126+
// 最小堆，降序排序，去注释
127+
public class Heap {
128+
private int n;
129+
130+
public int[] heapSort(int[] nums) {
131+
n = nums.length;
132+
for (int i = n / 2 - 1; i >= 0; i--) {
133+
minHeapify(nums, i);
134+
}
135+
while (n > 0) {
136+
swap(nums, 0, n - 1);
137+
n--;
138+
minHeapify(nums, 0);
139+
}
140+
return nums;
141+
}
142+
143+
private void minHeapify(int[] nums, int root) {
144+
int minIndex = root;
145+
int left = root * 2 + 1, right = root * 2 + 2;
146+
if (left < n && nums[left] < nums[minIndex])
147+
minIndex = left;
148+
if (right < n && nums[right] < nums[minIndex])
149+
minIndex = right;
150+
if (minIndex != root) {
151+
swap(nums, minIndex, root);
152+
minHeapify(nums, minIndex);
153+
}
154+
}
155+
156+
private void swap(int[] nums, int x, int y) {
157+
int temp = nums[x];
158+
nums[x] = nums[y];
159+
nums[y] = temp;
160+
}
161+
}

‎十大排序算法_Java/Quick.java

Lines changed: 42 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,53 @@
11
package sort;
22

3-
// 快速排序
3+
/*
4+
快速排序：
5+
1、一次排序操作将返回一个已经排好位置的中点索引mid，该索引左边的元素都小于它，右边的元素都大于等于它
6+
2、递归方法：
7+
1）方法功能：根据数组和指定左右边界，进行一次排序，然后返回排序后的数组
8+
2）终止条件：左边界大于等于右边界，说明只剩一个元素或边界无效，不用排序，直接返回数组
9+
3）递归逻辑：排序好的中点的左半部分和右半部分数组也需要同样的操作，调用同样的方法进行排序。数组是引用类型，不用接收递归方法返回值，最后直接返回数组即可
10+
*/
11+
12+
/*
13+
一次排序初始：
14+
3 2 3 1 2 4 5 5 6
15+
↑ ↑ ↑
16+
left index/i right
17+
============================================================
18+
一次排序遍历交换过程：
19+
3 2 3 1 2 4 5 5 6
20+
↑ ↑ ↑ ↑
21+
left index i right
22+
============================================================
23+
一次排序遍历结束，准备交换中点，index-1表示最后一个值小于left的索引：
24+
3 2 1 2 3 4 5 5 6
25+
↑ ↑ ↑ ↑ ↑
26+
left index-1 index right i
27+
============================================================
28+
一次排序结果：
29+
2 2 1 3 3 4 5 5 6
30+
↑
31+
mid
32+
============================================================
33+
下一次排序：
34+
2 2 1 3 3 4 5 5 6
35+
↑ ↑ ↑ ↑ ↑
36+
left mid-1 mid mid+1 right
37+
*/
438
public class Quick {
539
public int[] quickSort(int[] nums) {
640
return mainSort(nums, 0, nums.length - 1);
741
}
842

43+
// 递归方法
944
private int[] mainSort(int[] nums, int left, int right) {
10-
if (left < right) {
11-
int mid = partition(nums, left, right);
12-
// 递归排序左右两部分
13-
mainSort(nums, left, mid - 1);
14-
mainSort(nums, mid + 1, right);
45+
if (left >= right) {
46+
return nums;
1547
}
48+
int mid = partition(nums, left, right);
49+
mainSort(nums, left, mid - 1);
50+
mainSort(nums, mid + 1, right);
1651
return nums;
1752
}
1853

@@ -29,6 +64,7 @@ private int partition(int[] nums, int left, int right) {
2964
return index - 1;
3065
}
3166

67+
// 交换元素
3268
private void swap(int[] nums, int x, int y) {
3369
int temp = nums[x];
3470
nums[x] = nums[y];

0 commit comments

Comments
 (0)