Skip to content

Commit 6354e86

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0215. Kth Largest Element in an Array
1 parent 43d2ae9 commit 6354e86

File tree

6 files changed

+340
-94
lines changed

6 files changed

+340
-94
lines changed

‎solution/0200-0299/0215.Kth Largest Element in an Array/README.md

Lines changed: 124 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,22 +28,145 @@
2828

2929
<!-- 这里可写通用的实现逻辑 -->
3030

31+
快速排序 partition 实现。
32+
3133
<!-- tabs:start -->
3234

3335
### **Python3**
3436

3537
<!-- 这里可写当前语言的特殊实现逻辑 -->
3638

3739
```python
38-
40+
class Solution:
41+
def findKthLargest(self, nums: List[int], k: int) -> int:
42+
def quickSort(nums, left, right, k):
43+
if left == right:
44+
return nums[left]
45+
i, j = left - 1, right + 1
46+
x = nums[(left + right) >> 1]
47+
while i < j:
48+
while 1:
49+
i += 1
50+
if nums[i] >= x:
51+
break
52+
while 1:
53+
j -= 1
54+
if nums[j] <= x:
55+
break
56+
if i < j:
57+
nums[i], nums[j] = nums[j], nums[i]
58+
if j < k:
59+
return quickSort(nums, j + 1, right, k)
60+
return quickSort(nums, left, j, k)
61+
62+
n = len(nums)
63+
return quickSort(nums, 0, n - 1, n - k)
3964
```
4065

4166
### **Java**
4267

4368
<!-- 这里可写当前语言的特殊实现逻辑 -->
4469

4570
```java
71+
class Solution {
72+
public int findKthLargest(int[] nums, int k) {
73+
int n = nums.length;
74+
return quickSort(nums, 0, n - 1, n - k);
75+
}
76+
77+
private int quickSort(int[] nums, int left, int right, int k) {
78+
if (left == right) {
79+
return nums[left];
80+
}
81+
int i = left - 1, j = right + 1;
82+
int x = nums[(left + right) >>> 1];
83+
while (i < j) {
84+
while (nums[++i] < x);
85+
while (nums[--j] > x);
86+
if (i < j) {
87+
int t = nums[i];
88+
nums[i] = nums[j];
89+
nums[j] = t;
90+
}
91+
}
92+
if (j < k) {
93+
return quickSort(nums, j + 1, right, k);
94+
}
95+
return quickSort(nums, left, j, k);
96+
97+
}
98+
}
99+
```
100+
101+
### **C++**
102+
103+
```cpp
104+
class Solution {
105+
public:
106+
int findKthLargest(vector<int>& nums, int k) {
107+
int n = nums.size();
108+
return quickSort(nums, 0, n - 1, n - k);
109+
}
110+
111+
int quickSort(vector<int>& nums, int left, int right, int k) {
112+
if (left == right) {
113+
return nums[left];
114+
}
115+
int i = left - 1, j = right + 1;
116+
int x = nums[left + right >> 1];
117+
while (i < j) {
118+
while (nums[++i] < x);
119+
while (nums[--j] > x);
120+
if (i < j) {
121+
int t = nums[i];
122+
nums[i] = nums[j];
123+
nums[j] = t;
124+
}
125+
}
126+
if (j < k) {
127+
return quickSort(nums, j + 1, right, k);
128+
}
129+
return quickSort(nums, left, j, k);
130+
}
131+
};
132+
```
46133

134+
### **Go**
135+
136+
```go
137+
func findKthLargest(nums []int, k int) int {
138+
n := len(nums)
139+
return quickSort(nums, 0, n-1, n-k)
140+
}
141+
142+
func quickSort(nums []int, left, right, k int) int {
143+
if left == right {
144+
return nums[left]
145+
}
146+
i, j := left-1, right+1
147+
x := nums[(left+right)>>1]
148+
for i < j {
149+
for {
150+
i++
151+
if nums[i] >= x {
152+
break
153+
}
154+
}
155+
for {
156+
j--
157+
if nums[j] <= x {
158+
break
159+
}
160+
}
161+
if i < j {
162+
nums[i], nums[j] = nums[j], nums[i]
163+
}
164+
}
165+
if j < k {
166+
return quickSort(nums, j+1, right, k)
167+
}
168+
return quickSort(nums, left, j, k)
169+
}
47170
```
48171

49172
### **...**

‎solution/0200-0299/0215.Kth Largest Element in an Array/README_EN.md

Lines changed: 122 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -32,13 +32,134 @@
3232
### **Python3**
3333

3434
```python
35-
35+
class Solution:
36+
def findKthLargest(self, nums: List[int], k: int) -> int:
37+
def quickSort(nums, left, right, k):
38+
if left == right:
39+
return nums[left]
40+
i, j = left - 1, right + 1
41+
x = nums[(left + right) >> 1]
42+
while i < j:
43+
while 1:
44+
i += 1
45+
if nums[i] >= x:
46+
break
47+
while 1:
48+
j -= 1
49+
if nums[j] <= x:
50+
break
51+
if i < j:
52+
nums[i], nums[j] = nums[j], nums[i]
53+
if j < k:
54+
return quickSort(nums, j + 1, right, k)
55+
return quickSort(nums, left, j, k)
56+
57+
n = len(nums)
58+
return quickSort(nums, 0, n - 1, n - k)
3659
```
3760

3861
### **Java**
3962

4063
```java
64+
class Solution {
65+
public int findKthLargest(int[] nums, int k) {
66+
int n = nums.length;
67+
return quickSort(nums, 0, n - 1, n - k);
68+
}
69+
70+
private int quickSort(int[] nums, int left, int right, int k) {
71+
if (left == right) {
72+
return nums[left];
73+
}
74+
int i = left - 1, j = right + 1;
75+
int x = nums[(left + right) >>> 1];
76+
while (i < j) {
77+
while (nums[++i] < x);
78+
while (nums[--j] > x);
79+
if (i < j) {
80+
int t = nums[i];
81+
nums[i] = nums[j];
82+
nums[j] = t;
83+
}
84+
}
85+
if (j < k) {
86+
return quickSort(nums, j + 1, right, k);
87+
}
88+
return quickSort(nums, left, j, k);
89+
90+
}
91+
}
92+
```
93+
94+
### **C++**
95+
96+
```cpp
97+
class Solution {
98+
public:
99+
int findKthLargest(vector<int>& nums, int k) {
100+
int n = nums.size();
101+
return quickSort(nums, 0, n - 1, n - k);
102+
}
103+
104+
int quickSort(vector<int>& nums, int left, int right, int k) {
105+
if (left == right) {
106+
return nums[left];
107+
}
108+
int i = left - 1, j = right + 1;
109+
int x = nums[left + right >> 1];
110+
while (i < j) {
111+
while (nums[++i] < x);
112+
while (nums[--j] > x);
113+
if (i < j) {
114+
int t = nums[i];
115+
nums[i] = nums[j];
116+
nums[j] = t;
117+
}
118+
}
119+
if (j < k) {
120+
return quickSort(nums, j + 1, right, k);
121+
}
122+
return quickSort(nums, left, j, k);
123+
}
124+
};
125+
```
41126

127+
### **Go**
128+
129+
```go
130+
func findKthLargest(nums []int, k int) int {
131+
n := len(nums)
132+
return quickSort(nums, 0, n-1, n-k)
133+
}
134+
135+
func quickSort(nums []int, left, right, k int) int {
136+
if left == right {
137+
return nums[left]
138+
}
139+
i, j := left-1, right+1
140+
x := nums[(left+right)>>1]
141+
for i < j {
142+
for {
143+
i++
144+
if nums[i] >= x {
145+
break
146+
}
147+
}
148+
for {
149+
j--
150+
if nums[j] <= x {
151+
break
152+
}
153+
}
154+
if i < j {
155+
nums[i], nums[j] = nums[j], nums[i]
156+
}
157+
}
158+
if j < k {
159+
return quickSort(nums, j+1, right, k)
160+
}
161+
return quickSort(nums, left, j, k)
162+
}
42163
```
43164

44165
### **...**

‎solution/0200-0299/0215.Kth Largest Element in an Array/Solution.cpp

Lines changed: 22 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,44 +1,28 @@
11
class Solution {
22
public:
33
int findKthLargest(vector<int>& nums, int k) {
4-
--k ;
5-
int ii = 0, jj = nums.size()-1 ;
6-
int i, j ;
7-
while (true)
8-
{
9-
i = ii, j = jj ;
10-
if (i + 63 < j)
11-
{
12-
const int mid = i + (j-i)/2 ;
13-
if (nums[j] >= nums[mid] && nums[j] <= nums[i]
14-
|| nums[j] <= nums[mid] && nums[j] >= nums[i])
15-
{
16-
swap(nums[i], nums[j]) ;
17-
}
18-
else if (nums[mid] >= nums[i] && nums[mid] <= nums[j]
19-
|| nums[mid] <= nums[i] && nums[mid] >= nums[j])
20-
{
21-
swap(nums[i], nums[mid]) ;
22-
}
23-
}
24-
while (i < j)
25-
{
26-
while (i < j && nums.at(i) >= nums.at(j))
27-
--j ;
28-
swap(nums[i], nums[j]) ;
29-
while (i < j && nums.at(i) >= nums.at(j))
30-
++i ;
31-
swap(nums[i], nums[j]) ;
4+
int n = nums.size();
5+
return quickSort(nums, 0, n - 1, n - k);
6+
}
7+
8+
int quickSort(vector<int>& nums, int left, int right, int k) {
9+
if (left == right) {
10+
return nums[left];
11+
}
12+
int i = left - 1, j = right + 1;
13+
int x = nums[left + right >> 1];
14+
while (i < j) {
15+
while (nums[++i] < x);
16+
while (nums[--j] > x);
17+
if (i < j) {
18+
int t = nums[i];
19+
nums[i] = nums[j];
20+
nums[j] = t;
3221
}
33-
34-
if (i > k)
35-
jj = i-1 ;
36-
else if (i < k)
37-
ii = i+1 ;
38-
else
39-
return nums[k] ;
4022
}
41-
42-
return nums.at(k) ;
23+
if (j < k) {
24+
return quickSort(nums, j + 1, right, k);
25+
}
26+
return quickSort(nums, left, j, k);
4327
}
44-
};
28+
};

0 commit comments

Comments
 (0)