侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【排序, 前缀和, 二分查找】和有限的最长子序列

GabrielxD
2022-08-29 / 0 评论 / 0 点赞 / 46 阅读 / 782 字 / 正在检测是否收录...

题目

6160. 和有限的最长子序列


给你一个长度为 n 的整数数组 nums ,和一个长度为 m 的整数数组 queries

返回一个长度为 m 的数组 answer ,其中 answer[i]nums 中 元素之和小于等于 queries[i]子序列最大 长度。

子序列 是由一个数组删除某些元素(也可以不删除)但不改变剩余元素顺序得到的一个数组。

示例 1:

输入:nums = [4,5,2,1], queries = [3,10,21]
输出:[2,3,4]
解释:queries 对应的 answer 如下:
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ,所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ,所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ,所以 answer[2] = 4 。

示例 2:

输入:nums = [2,3,4,5], queries = [1]
输出:[0]
解释:空子序列是唯一一个满足元素和小于或等于 1 的子序列,所以 answer[0] = 0 。

提示:

  • n == nums.length
  • m == queries.length
  • 1 <= n, m <= 1000
  • 1 <= nums[i], queries[i] <= 10^6

解题

方法一:排序 前缀和 二分查找

思路

首先,要求的是子序列的最大长度,因为子序列可以通过增删元素得到,也就意味着数组可以排序,而子序列的最大长度又与子序列的和有关,所以应该先把数组升序排序。

然后问题就变成了求 nums 中元素之和小于等于 queries[i]前缀子数组的最大长度,这里提到了子数组元素之和,自然可以想到用前缀和求解,于是构造数组的前缀和数组。

那么问题就变成了求**前缀和数组**中小于等于 queries[i] 的元素中最靠右的位置。在有序数组中求元素位置可以使用二分查找进行优化,具体需要用到:二分查找 - 整数二分 - 小于等于

求出位置后覆盖 queries 数组最后返回即可。

代码

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            prefixSums[i] = nums[i - 1] + prefixSums[i - 1];
        }
        for (int i = 0; i < queries.length; ++i) {
            int query = queries[i];
            int l = 0, r = n;
            while (l < r) {
                int c = l + r + 1 >> 1;
                if (prefixSums[c] <= query) l = c;
                else r = c - 1;
            }
            queries[i] = l;
        }
        return queries;
    }
}

std::upper_bound

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> prefix_sums(n + 1);
        for (int i = 0; i < n; ++i) {
            prefix_sums[i + 1] = prefix_sums[i] + nums[i];
        }
        for (int& query : queries) {
            query = upper_bound(prefix_sums.begin(), prefix_sums.end(), query)- prefix_sums.begin() - 1;
        }
        return queries;
    }
};
0

评论区