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
| class Solution {
public:
void buildHeap(vector<pair<int,int>>& nums) {
for(int i = nums.size() / 2 - 1; i >= 0; i --) {
maxifyHeap(nums, i, nums.size());
}
}
void maxifyHeap(vector<pair<int,int>>& nums, int i, int heapSize) {
int left = i * 2 + 1, right = left + 1, maxn = i;
if(left < heapSize && nums[left].first > nums[maxn].first) {
maxn = left;
}
if(right < heapSize && nums[right].first > nums[maxn].first) {
maxn = right;
}
if(maxn != i ) {
swap(nums[maxn], nums[i]);
maxifyHeap(nums, maxn, heapSize);
}
}
vector<int> maxSubsequence(vector<int>& nums, int k) {
vector<int> sub(k);
vector<pair<int,int>> numsToIndex(nums.size());
for(int i = 0; i < nums.size(); i ++) {
numsToIndex[i] = make_pair(nums[i], i);
}
buildHeap(numsToIndex);
for(int i = 0; i < k; i ++) {
sub[i] = numsToIndex[0].second;
swap(numsToIndex[0], numsToIndex[nums.size() - i - 1]);
maxifyHeap(numsToIndex, 0, nums.size() - i - 1);
}
sort(sub.begin(), sub.end());
vector<int> ans(k);
for(int i = 0; i < k; i ++) {
ans[i] = nums[sub[i]];
}
return ans;
}
};
|
