Posts tagged as “quickselect”

花花酱 LeetCode 2099. Find Subsequence of Length K With the Largest Sum

By zxi on December 12, 2021

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
-10⁵ <= nums[i] <= 10⁵
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++

// 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++

// 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;

}

};

花花酱 LeetCode 1471. The k Strongest Values in an Array

By zxi on June 6, 2020

Given an array of integers arr and an integer k.

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).

For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.

Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.

Example 2:

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].

Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.

Example 4:

Input: arr = [6,-3,7,2,11], k = 3
Output: [-3,11,2]

Example 5:

Input: arr = [-7,22,17,3], k = 2
Output: [22,17]

Constraints:

1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length

Solution 1: quick selection + sort

Step 1: find the median element m
Step 2: Sort the array according to m
Step 3: output the first k elements of the sorted array.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> getStrongest(vector<int>& arr, int k) {

const int n = arr.size();

const int i = (n - 1) / 2;

// sort(begin(arr), end(arr));

nth_element(begin(arr), begin(arr) + i, end(arr));

const int m = arr[i];

sort(begin(arr), end(arr), [&](const int x, const int y) {

return abs(x - m) != abs(y - m) ? abs(x - m) > abs(y - m) : x > y;

});

return {begin(arr), begin(arr) + k};

}

};

花花酱 LeetCode 1387. Sort Integers by The Power Value

By zxi on March 22, 2020

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

if x is even then x = x / 2
if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1).

Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

Return the k-th integer in the range [lo, hi] sorted by the power value.

Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.

Example 1:

Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Example 2:

Input: lo = 1, hi = 1, k = 1
Output: 1

Example 3:

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

Example 4:

Input: lo = 10, hi = 20, k = 5
Output: 13

Example 5:

Input: lo = 1, hi = 1000, k = 777
Output: 570

Constraints:

1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1

Solution: Precompute + quick select

Time complexity: O(nlogn) + O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int getKth(int lo, int hi, int k) {

vector<pair<int, int>> vals;

for (int n = lo; n <= hi; ++n) {

int p = 0;

int x = n;

while (x != 1) {

if (x & 1) x = 3 * x + 1;

else x /= 2;

++p;

}

vals.emplace_back(p, n);

}

nth_element(begin(vals), begin(vals) + k - 1, end(vals));

return vals[k - 1].second;

}

};