顺利遍历、二分查找 2 种算法（手写实现 bisect.bisect_right / upper_bound），用降序排列和前缀和技巧，求解《1403. 非递增顺序的最小子序列》
例题
1403. 非递增顺序的最小子序列
给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。
注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
示例 1：
输入：nums = [4,3,10,9,8]
输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。
答案
顺序遍历 · 降序排列
var minSubsequence = function(nums) {
const n = nums.length, tSum = _.sum(nums), r = []
nums.sort((a, b) => b - a)
let pSum = 0
for (let i = 0; i < n; i++) {
pSum += nums[i]
r[i] = nums[i]
if (pSum << 1> tSum) return r
}
};function minSubsequence(nums: number[]): number[] {
const n = nums.length, tSum = _.sum(nums)
nums.sort((a, b) => b - a)
let lSum = 0
for (let i = 0; i < n; i++) {
lSum += nums[i]
if (lSum << 1 > tSum) return nums.slice(0, i + 1)
}
};class Solution {
function minSubsequence($nums) {
$n = sizeof($nums);
usort($nums, function($a, $b) {
return $a < $b;
});
$tSum = array_sum($nums);
$lSum = 0;
for ($i = 0; $i < $n; $i++) {
$lSum += $nums[$i];
if ($lSum << 1 > $tSum) return array_slice($nums, 0, $i + 1);
}
}
}func minSubsequence(nums []int) []int {
sort.SliceStable(nums, func(i, j int) bool {
return nums[i] > nums[j]
})
tSum, lSum := 0, 0
for _, num := range nums {
tSum += num
}
for i, num := range nums {
lSum += num
if lSum << 1 > tSum {
return nums[:i + 1]
}
}
return nil // 有限循环：返回值不可省略
}func minSubsequence(nums []int) []int {
sort.SliceStable(nums, func(i, j int) bool {
return nums[i] > nums[j]
})
tSum, lSum := 0, 0
for _, num := range nums {
tSum += num
}
for i := 0; ; i++ { // 无限循环包含 return ：省略不必要返回值
lSum += nums[i]
if lSum << 1 > tSum {
return nums[:i + 1]
}
}
}class Solution {
public List<Integer> minSubsequence(int[] nums) {
int n = nums.length, tSum = Arrays.stream(nums).sum(), lSum = 0;
Arrays.sort(nums); // 先升序，再倒序遍历
List<Integer> r = new ArrayList<Integer>();
for (int i = n - 1; ; i--) {
lSum += nums[i];
r.add(nums[i]);
if (lSum << 1 > tSum) return r;
}
}
}public class Solution {
public IList<int> MinSubsequence(int[] nums) {
int n = nums.Length, tSum = nums.Sum(), lSum = 0;
Array.Sort(nums, delegate(int a, int b) {
return b - a;
});
IList<int> r = new List<int>();
for (int i = 0; ; i++) {
lSum += nums[i];
r.Add(nums[i]);
if (lSum << 1 > tSum) return r;
}
}
}static inline int cmp(const void *pa, const void *pb) {
return *(int *)pb - *(int *)pa;
}
int* minSubsequence(int* nums, int numsSize, int* returnSize){
qsort(nums, numsSize, sizeof(int), cmp);
int tSum = 0;
for (int i = 0; i < numsSize; i++) {
tSum += nums[i];
}
int *r = malloc(sizeof(int) * numsSize);
for (int i = 0, lSum = 0; i < numsSize; i++) {
lSum += nums[i];
r[i] = nums[i];
if (lSum << 1 > tSum) {
*returnSize = i + 1;
break;
}
}
return r;
}class Solution {
public:
vector<int> minSubsequence(vector<int>& nums) {
sort(nums.begin(), nums.end(), greater<int>());
int tSum = accumulate(nums.begin(), nums.end(), 0);
int n = nums.size();
for (int i = 0, lSum = 0; ; i++) {
lSum += nums[i];
if (lSum << 1 > tSum) {
vector<int> r(i + 1);
copy(nums.begin(), nums.begin() + i + 1, r.begin());
return r;
}
}
}
};class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
n, tSum, lSum = len(nums), sum(nums), 0
nums.sort(key = lambda k: -k) # lambda 降序
for i, num in enumerate(nums):
lSum += num
if lSum << 1 > tSum: return nums[:i + 1]class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
n, tSum, lSum = len(nums), sum(nums), 0
nums.sort(reverse = True) # reverse 降序
for i, num in enumerate(nums):
lSum += num
if lSum << 1 > tSum: return nums[:i + 1]二分查找 · 降序排列 · 前缀和
var minSubsequence = function(nums) {
const n = nums.length, sums = new Uint16Array(n + 1)
nums.sort((a, b) => b - a)
for (let i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1]
}
return nums.slice(0, upper_bound(sums, sums[n] >>> 1))
};
const upper_bound = (nums, num) => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] > num) r = m - 1
else l = m + 1
}
return l
}function minSubsequence(nums: number[]): number[] {
const n = nums.length, sums = new Array(n + 1)
sums[0] = 0
nums.sort((a, b) => b - a)
for (let i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1]
}
return nums.slice(0, upper_bound(sums, sums[n] >>> 1))
};
function upper_bound(nums: number[], num: number): number {
let l = 0, r = nums.length - 1
while(l <= r) {
const m = l + r >>> 1
if (nums[m] > num) r = m - 1
else l = m + 1
}
return l
}class Solution {
function minSubsequence($nums) {
$n = count($nums);
usort($nums, function($a, $b) {
return $a < $b;
});
$sums = array_fill(0, $n + 1, 0);
for ($i = 1; $i <= $n; $i++) {
$sums[$i] = $sums[$i - 1] + $nums[$i - 1];
}
return array_slice($nums, 0, $this->upper_bound($sums, $sums[$n] >> 1));
}
function upper_bound(&$nums, $num) {
$l = 0;
$r = count($nums) - 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($nums[$m] > $num) $r = $m - 1;
else $l = $m + 1;
}
return $l;
}
}func minSubsequence(nums []int) []int {
sort.SliceStable(nums, func(i, j int) bool {
return nums[i] > nums[j]
})
n := len(nums)
sums := make([]int, n + 1)
for i := 1; i <= n; i++ {
sums[i] = sums[i - 1] + nums[i - 1]
}
return nums[:upper_bound(sums, sums[n] >> 1)]
}
func upper_bound(nums []int, num int) int { // 自行实现
l, r := 0, len(nums) - 1
for l <= r {
m := (l + r) >> 1
if nums[m] > num {
r = m - 1
} else {
l = m + 1
}
}
return l
}func minSubsequence(nums []int) []int {
sort.SliceStable(nums, func(i, j int) bool {
return nums[i] > nums[j]
})
n := len(nums)
sums := make([]int, n + 1)
for i := 1; i <= n; i++ {
sums[i] = sums[i - 1] + nums[i - 1]
}
return nums[:sort.Search(n, func(i int) bool { // golang 函数库
return sums[i] > sums[n] >> 1
})]
}class Solution {
public List<Integer> minSubsequence(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] sums = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
sums[n - i] = sums[n - i - 1] + nums[i];
}
int j = upper_bound(sums, sums[n] >>> 1);
List<Integer> r = new ArrayList<Integer>();
for (int i = n - 1, k = 0; k < j; i--, k++) {
r.add(nums[i]);
}
return r;
}
public int upper_bound(int[] nums, int num) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = l + r >>> 1;
if (nums[m] > num) r = m - 1;
else l = m + 1;
}
return l;
}
}public class Solution {
public IList<int> MinSubsequence(int[] nums) {
int n = nums.Length;
Array.Sort(nums, delegate(int a, int b) {
return b - a;
});
int[] sums = new int[n + 1];
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
int j = upper_bound(sums, sums[n] >> 1);
IList<int> r = new List<int>();
for (int i = 0; i < j; i++) {
r.Add(nums[i]);
}
return r;
}
public int upper_bound(int[] nums, int num) {
int l = 0, r = nums.Length - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] > num) r = m - 1;
else l = m + 1;
}
return l;
}
}static inline int cmp(const void *pa, const void *pb) {
return *(int *)pb - *(int *)pa;
}
int upper_bound(int* nums, int numsSize, int num) {
int l = 0, r = numsSize - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] > num) r = m - 1;
else l = m + 1;
}
return l;
}
int* minSubsequence(int* nums, int numsSize, int* returnSize){
qsort(nums, numsSize, sizeof(int), cmp);
int* sums = malloc(sizeof(int) * (numsSize + 1));
sums[0] = 0;
for (int i = 1; i <= numsSize; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
int j = upper_bound(sums, numsSize, sums[numsSize] >> 1);
int* r = malloc(sizeof(int) * numsSize);
for (int i = 0; i < j; i++) {
r[i] = nums[i];
}
*returnSize = j;
return r;
}class Solution {
public:
vector<int> minSubsequence(vector<int>& nums) {
sort(nums.begin(), nums.end(), greater<int>());
int n = nums.size();
vector<int> sums(n + 1);
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
int i = upper_bound(sums, sums[n] >> 1);
vector<int> r(i);
copy(nums.begin(), nums.begin() + i, r.begin());
return r;
}
int upper_bound(vector<int>& nums, int num) { // 自行实现
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] > num) r = m - 1;
else l = m + 1;
}
return l;
}
};class Solution {
public:
vector<int> minSubsequence(vector<int>& nums) {
sort(nums.begin(), nums.end(), greater<int>());
int n = nums.size();
vector<int> sums(n + 1);
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
vector<int>::iterator i = upper_bound(sums.begin(), sums.end(), sums[n] >> 1); // 自带函数
int j = i - sums.begin();
vector<int> r(j);
copy(nums.begin(), nums.begin() + j, r.begin());
return r;
}
};class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
nums.sort(key = lambda k: -k) # lambda 降序
n = len(nums)
sums = [0] * (n + 1)
for i in range(1, n + 1): sums[i] = sums[i - 1] + nums[i - 1]
return nums[:bisect.bisect_right(sums, sums[n] >> 1)]class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
nums.sort(reverse = True) # reverse 降序
n = len(nums)
sums = [0] * (n + 1)
for i in range(1, n + 1): sums[i] = sums[i - 1] + nums[i - 1]
return nums[:bisect.bisect_right(sums, sums[n] >> 1)]