8000 solve problem Kth Largest Element In An Array · P-ppc/leetcode@2847082 · GitHub
[go: up one dir, main page]
Skip to content

Commit 2847082

Browse files
P-ppcP-ppc
committed
solve problem Kth Largest Element In An Array
1 parent 21f1f5f commit 2847082

File tree

5 files changed

+197
-1
lines changed

5 files changed

+197
-1
lines changed

‎README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -313,7 +313,8 @@ All solutions will be accepted!
313313
|394|[Decode String](https://leetcode-cn.com/problems/decode-string/description/)|[java/py/js](./algorithms/DecodeString)|Medium|
314314
|938|[Range Sum Of Bst](https://leetcode-cn.com/problems/range-sum-of-bst/description/)|[java/py/js](./algorithms/RangeSumOfBst)|Medium|
315315
|71|[Simplify Path](https://leetcode-cn.com/problems/simplify-path/description/)|[java/py/js](./algorithms/SimplifyPath)|Medium|
316-
|451|[Sort Characters By Frequency](https://leetcode-cn.com/problems/sort-characters-by-frequency/description/)|[java/py/js](./SortCharactersByFrequency)|Medium|
316+
|451|[Sort Characters By Frequency](https://leetcode-cn.com/problems/sort-characters-by-frequency/description/)|[java/py/js](./algorithms/SortCharactersByFrequency)|Medium|
317+
|215|[Kth Largest Element In An Array](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/description/)|[java/py/js](./algorithms/KthLargestElementInAnArray)|Medium|
317318

318319
# Database
319320
|#|Title|Solution|Difficulty|

‎algorithms/KthLargestElementInAnArray/README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
# Kth Largest Element In An Array
2+
We can solve this problem by max heap

‎algorithms/KthLargestElementInAnArray/Solution.java

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
class Solution {
2+
class MaxHeap {
3+
ArrayList<Integer> heap;
4+
5+
MaxHeap() {
6+
heap = new ArrayList<Integer>();
7+
}
8+
9+
void push(int value) {
10+
heap.add(value);
11+
int pos = heap.size() - 1;
12+
int pPos = (pos % 2 == 0 ? pos - 2 : pos - 1) / 2;
13+
14+
while (pPos >= 0 && value > heap.get(pPos)) {
15+
heap.set(pos, heap.get(pPos));
16+
heap.set(pPos, value);
17+
pos = pPos;
18+
pPos = (pos % 2 == 0 ? pos - 2 : pos - 1) / 2;
19+
}
20+
}
21+
22+
int size() {
23+
return heap.size();
24+
}
25+
26+
int pop() {
27+
int size = heap.size();
28+
if (size == 0)
29+
throw new ArrayIndexOutOfBoundsException("pop from empty list");
30+
else if (size == 1)
31+
return heap.remove(0);
32+
33+
int value = heap.get(0);
34+
heap.set(0, heap.remove(size - 1));
35+
int pos = 0;
36+
int maxChildPos = pos * 2 + 2;
37+
if (maxChildPos < size - 1)
38+
maxChildPos = heap.get(maxChildPos) > heap.get(maxChildPos - 1) ? maxChildPos : maxChildPos - 1;
39+
else
40+
maxChildPos = maxChildPos - 1 < size - 1 ? maxChildPos - 1 : pos;
41+
42+
while (maxChildPos < size - 1 && heap.get(pos) < heap.get(maxChildPos)) {
43+
int temp = heap.get(maxChildPos);
44+
heap.set(maxChildPos, heap.get(pos));
45+
heap.set(pos, temp);
46+
pos = maxChildPos;
47+
maxChildPos = pos * 2 + 2;
48+
49+
if (maxChildPos < size - 1)
50+
maxChildPos = heap.get(maxChildPos) > heap.get(maxChildPos - 1) ? maxChildPos : maxChildPos - 1;
51+
else
52+
maxChildPos = maxChildPos - 1 < size - 1 ? maxChildPos - 1 : pos;
53+
}
54+
55+
return value;
56+
}
57+
}
58+
59+
public int findKthLargest(int[] nums, int k) {
60+
MaxHeap maxHeap = new MaxHeap();
61+
for (int num : nums)
62+
maxHeap.push(num);
63+
for (int i = 0; i < k - 1; i++)
64+
maxHeap.pop();
65+
return maxHeap.pop();
66+
}
67+
}

‎algorithms/KthLargestElementInAnArray/solution.js

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
/**
2+
* @param {number[]} nums
3+
* @param {number} k
4+
* @return {number}
5+
*/
6+
var findKthLargest = function(nums, k) {
7+
let maxHeap = new MaxHeap()
8+
nums.forEach(num => maxHeap.push(num))
9+
for (let i = 0; i < k - 1; i++)
10+
maxHeap.pop()
11+
return maxHeap.pop()
12+
};
13+
14+
function MaxHeap() {
15+
this.heap = []
16+
};
17+
18+
MaxHeap.prototype.push = function(value) {
19+
this.heap.push(value)
20+
let pos = this.heap.length - 1,
21+
pPos = (pos % 2 == 0 ? pos - 2 : pos - 1) / 2
22+
23+
while (pPos >= 0 && value > this.heap[pPos]) {
24+
let temp = this.heap[pPos]
25+
this.heap[pPos] = value
26+
this.heap[pos] = temp
27+
pos = pPos
28+
pPos = (pos % 2 == 0 ? pos - 2 : pos - 1) / 2
29+
}
30+
};
31+
32+
MaxHeap.prototype.size = function() {
33+
return this.heap.length
34+
};
35+
36+
MaxHeap.prototype.pop = function() {
37+
let size = this.heap.length
38+
if (size == 0)
39+
throw new Error('pop form empty list')
40+
else if (size == 1)
41+
return this.heap.pop()
42+
43+
let value = this.heap[0],
44+
pos = 0,
45+
maxChildPos = pos * 2 + 2
46+
this.heap[0] = this.heap.pop()
47+
48+
if (maxChildPos < size - 1)
49+
maxChildPos = this.heap[maxChildPos] > this.heap[maxChildPos - 1] ? maxChildPos : maxChildPos - 1
50+
else
51+
maxChildPos = maxChildPos - 1 < size - 1 ? maxChildPos - 1 : pos
52+
53+
while (maxChildPos < size - 1 && this.heap[pos] < this.heap[maxChildPos]) {
54+
let temp = this.heap[maxChildPos]
55+
this.heap[maxChildPos] = this.heap[pos]
56+
this.heap[pos] = temp
57+
pos = maxChildPos
58+
maxChildPos = pos * 2 + 2
59+
60+
if (maxChildPos < size - 1)
61+
maxChildPos = this.heap[maxChildPos] > this.heap[maxChildPos - 1] ? maxChildPos : maxChildPos - 1
62+
else
63+
maxChildPos = maxChildPos - 1 < size - 1 ? maxChildPos - 1 : pos
64+
}
65+
66+
return value
67+
};

‎algorithms/KthLargestElementInAnArray/solution.py

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
class Solution(object):
2+
class MaxHeap(object):
3+
def __init__(self):
4+
self.heap = []
5+
6+
def push(self, value):
7+
self.heap.append(value)
8+
pos = len(self.heap) - 1
9+
p_pos = (pos - 2 if pos % 2 == 0 else pos - 1) / 2
10+
11+
while p_pos >= 0 and value > self.heap[p_pos]:
12+
self.heap[pos], self.heap[p_pos] = self.heap[p_pos], self.heap[pos]
13+
pos = p_pos
14+
p_pos = (pos - 2 if pos % 2 == 0 else pos - 1) / 2
15+
16+
17+
def size(self):
18+
return len(self.heap)
19+
20+
def pop(self):
21+
size = len(self.heap)
22+
if size == 0:
23+
raise IndexError('pop from empty list')
24+
elif size == 1:
25+
return self.heap.pop()
26+
27+
value = self.heap[0]
28+
self.heap[0] = self.heap C .pop()
29+
pos = 0
30+
max_child_pos = pos * 2 + 2
31+
if max_child_pos < size - 1:
32+
max_child_pos = max_child_pos if self.heap[max_child_pos] > self.heap[max_child_pos - 1] else max_child_pos - 1
33+
else:
34+
max_child_pos = max_child_pos - 1 if max_child_pos - 1 < size - 1 else pos
35+
36+
while max_child_pos < size - 1 and self.heap[pos] < self.heap[max_child_pos]:
37+
self.heap[pos], self.heap[max_child_pos] = self.heap[max_child_pos], self.heap[pos]
38+
pos = max_child_pos
39+
max_child_pos = pos * 2 + 2
40+
if max_child_pos < size - 1:
41+
max_child_pos = max_child_pos if self.heap[max_child_pos] > self.heap[max_child_pos - 1] else max_child_pos - 1
42+
else:
43+
max_child_pos = max_child_pos - 1 if max_child_pos - 1 < size - 1 else pos
44+
return value
45+
46+
def findKthLargest(self, nums, k):
47+
"""
48+
:type nums: List[int]
49+
:type k: int
50+
:rtype: int
51+
"""
52+
max_heap = Solution.MaxHeap()
53+
for num in nums:
54+
max_heap.push(num)
55+
56+
for i in xrange(k - 1):
57+
max_heap.pop()
58+
59+
return max_heap.pop()

0 commit comments

Comments
 (0)
0