You are given an integer array nums
and an integer k
. You want to find a subsequence of nums
of length k
that has the largest sum.
Return any such subsequence as an integer array of length k
.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [2,1,3,3], k = 2 Output: [3,3] Explanation: The subsequence has the largest sum of 3 + 3 = 6.
Example 2:
Input: nums = [-1,-2,3,4], k = 3 Output: [-1,3,4] Explanation: The subsequence has the largest sum of -1 + 3 + 4 = 6.
Example 3:
Input: nums = [3,4,3,3], k = 2 Output: [3,4] Explanation: The subsequence has the largest sum of 3 + 4 = 7. Another possible subsequence is [4, 3].
Constraints:
1 <= nums.length <= 1000
-105 <= nums[i] <= 105
1 <= k <= nums.length
Solution 1: Full sorting + Hashtable
Make a copy of the original array, sort it in whole and put k largest elements in a hashtable.
Scan the original array and append the number to the answer array if it’s in the hashtable.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: vector<int> maxSubsequence(vector<int>& nums, int k) { vector<int> ans; vector<int> s(nums); sort(rbegin(s), rend(s)); unordered_map<int, int> m; for (int i = 0; i < k; ++i) ++m[s[i]]; for (int x : nums) if (--m[x] >= 0) ans.push_back(x); return ans; } }; |
Solution 2: k-th element
Use quick select / partial sort to find the k-th largest element of the array. Any number greater than that must be in the sequence. The tricky part is: what about the pivot itself? We couldn’t include ’em all blindly. Need to figure out how many copies of the pivot is there in the k largest and only include as many as of that in the final answer.
Time complexity: O(n+k)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: vector<int> maxSubsequence(vector<int>& nums, int k) { vector<int> ans; vector<int> s(nums); nth_element(begin(s), begin(s) + k - 1, end(s), greater<int>()); const int pivot = s[k - 1]; // How many pivots in the largest k elements. int left = count(begin(s), begin(s) + k, pivot); for (size_t i = 0; i != nums.size(); ++i) if (nums[i] > pivot || (nums[i] == pivot && --left >= 0)) ans.push_back(nums[i]); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment