贪心与优先队列相结合:如何高效求解最大子序列分数
贪心与优先队列相结合:如何高效求解最大子序列分数
在这篇文章中,我们将详细讲解如何从两个长度相同的数组 nums1
和 nums2
中选择 k
个元素的子序列,从而找到最大子序列分数。这道题目要求我们从 nums1
和 nums2
中分别选择相同索引的 k
个元素,然后计算 nums1
中选定元素的和,并乘以它们在 nums2
中的最小值。最后返回所有可能子序列组合中的最大分数。
问题分析
1. 题目理解与示例
给定两个相同长度的数组 nums1
和 nums2
,目标是选择 k
个元素的子序列,计算这些元素在 nums1
中的和,并乘以它们在 nums2
中的最小值,最后找到所有可能组合中分数的最大值。
举例说明:
-
示例 1:
输入: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3 输出: 24 解释: 选择子序列为 [3,3,2],对应 nums2 的最小值为 2,则分数为 (3+3+2)*2 = 24。
-
示例 2:
输入: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1 输出: 30 解释: 选择 nums1 中的任意一个元素,乘以其对应 nums2 中的值即可得到最大分数。
2. 思路分析
为了更好地理解问题,我们需要考虑几个方面:
-
如何选择子序列?
- 从
nums1
中选择k
个元素,并对应在nums2
中选择同样索引的元素。
- 从
-
如何最大化分数?
- 分数计算为
nums1
选择 元素的和sum
乘以nums2
中选定元素的 最小值min(nums2_selected)
。 - 因此,我们希望尽量选择
nums1
中较大的k
个数,同时选择nums2
中最小值较大的组合。
- 分数计算为
-
复杂度与优化方向
- 由于组合数量巨大,使用暴力枚举的方式会超时。我们需要一种高效的策略来筛选组合,从而减少计算量。
3. 常见错误与优化方向
如果使用暴力枚举所有可能的子序列组合,那么复杂度为
O
(
(
n
k
)
)
=
n
!
k
!
(
n
−
k
)
!
O(\binom{n}{k}) = \frac{n!}{k!(n-k)!}
O((kn))=k!(n−k)!n!,这是指数级别的复杂度,显然不适用于较大的 n
和 k
。
因此,我们需要考虑使用贪心算法和优先队列(堆)来优化解决方案。
优化解法:贪心 + 优先队列
1. 思路阐述
通过观察题目,我们可以发现以下贪心策略:
- 我们希望
nums2
中的最小值尽可能大,因为它作为分数计算的乘数,影响最大。 - 因此,我们可以优先选择
nums2
中较大的元素进行组合,然后在这些组合中选择nums1
中较大的元素。
为了实现这一策略:
-
排序与配对:
- 首先,我们将
nums1
和nums2
配对,形成(nums2[i], nums1[i])
的对组,然后按照nums2
的值从大到小进行排序。 - 这样一来,我们在遍历时,可以保证每次遍历到的
nums2
的值是当前所有未遍历元素中的最大值,从而尽可能增加分数中的乘数值。
- 首先,我们将
-
优先队列维护最大
k
个nums1
:- 使用一个优先队列(最小堆)来维护当前
nums1
中的前k
大元素的和。 - 当堆中元素数量超过
k
个时,移除堆顶元素(最小值),保证堆中始终包含k
个最大的nums1
元素。
- 使用一个优先队列(最小堆)来维护当前
-
计算分数与更新结果:
- 每次遍历到
k
个元素时,计算当前组合的分数,即sum(nums1_selected) * min(nums2_selected)
。 - 更新当前的最大分数。
- 每次遍历到
2. 代码实现
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size();
// 1. 创建配对数组,并按 nums2 从大到小排序
vector<pair<int, int>> pairs(n);
for (int i = 0; i < n; ++i) {
pairs[i] = {nums2[i], nums1[i]};
}
sort(pairs.rbegin(), pairs.rend()); // 按照 nums2 降序排列
// 2. 使用最小堆来维护 nums1 中最大的 k 个数
priority_queue<int, vector<int>, greater<int>> minHeap;
long long sum = 0, result = 0;
// 3. 遍历排序后的数组
for (int i = 0; i < n; ++i) {
int num1 = pairs[i].second;
int num2 = pairs[i].first;
// 将当前 num1 加入堆中
minHeap.push(num1);
sum += num1;
// 如果堆中元素超过了 k 个,移除最小的那个
if (minHeap.size() > k) {
sum -= minHeap.top();
minHeap.pop();
}
// 如果堆中的元素正好是 k 个,计算当前的分数
if (minHeap.size() == k) {
result = max(result, sum * num2); // 当前 sum * nums2 中的最小值
}
}
return result;
}
};
3. 代码详解
-
排序操作:
- 将
nums1
和nums2
的元素进行配对,生成(nums2[i], nums1[i])
的形式,并按照nums2
的值从大到小进行排序。 - 排序的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
- 将
-
优先队列维护前
k
大元素:- 使用最小堆(优先队列)来维护当前选定的
k
个nums1
元素的和。 - 每次加入一个新的元素时,如果堆中元素超过
k
,则移除堆顶最小元素,以保证堆中是当前最大的k
个元素。
- 使用最小堆(优先队列)来维护当前选定的
-
分数计算与结果更新:
- 当堆中元素达到
k
个时,计算当前组合的分数。 - 分数等于堆中
nums1
元素的和sum
,乘以当前nums2
中的最小值(因为是按降序排列,所以nums2
中的最小值就是当前遍历的元素)。
- 当堆中元素达到
4. 时间复杂度分析
- 排序: O ( n log n ) O(n \log n) O(nlogn)。
- 堆操作: 遍历每个元素并对堆进行插入或删除操作,每次操作的时间复杂度为 O ( log k ) O(\log k) O(logk),因此总的时间复杂度为 O ( n log k ) O(n \log k) O(nlogk)。
总时间复杂度为 O ( n log n ) O(n \log n) O(nlogn),相对于暴力枚举的指数级复杂度,这种方式显著提升了算法的效率。
示例讲解
示例 1:
输入:nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
-
首先,我们对
nums2
从大到小进行排序:- 排序后的配对数组为
[(4, 2), (3, 3), (2, 1), (1, 3)]
。
- 排序后的配对数组为
-
使用最小堆维护
k = 3
个最大的nums1
元素:- 第一个配对
(4, 2)
:加入堆,当前堆为[2]
,和为2
,当前最小nums2
为4
,暂时不计算。 - 第二个配对
(3, 3)
:加入堆,当前堆为[2, 3]
,和为5
,当前最小nums2
为3
,暂时不计算。 - 第三个配对
(3, 3)
:加入堆,当前堆为[2, 3, 3]
,和为8
,此时堆中有 3 个元素,可以计算分数为8 * 3 = 24
。 - 第四个配对
(2, 1)
:堆已满,且此时堆顶最小元素为2
,替换后和不变,最终分数为24
。
- 第一个配对
输出:24
。
示例 2:
输入:nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
-
对
nums2
从大到小排序:- 排序后的配对数组为
[(10, 3), (9, 1), (7, 4), (6, 1), (5, 2)]
。
- 排序后的配对数组为
-
使用最小堆维护
k = 1
个最大的nums1
元素:- 第一个配对
(10, 3)
:堆中元素为[3]
,分数为3 * 10 = 30
。 - 后续配对都不比此分数大,最终结果为
30
。
- 第一个配对
输出:30
。
总结
通过贪心策略和优先队列的结合,我们能够高效解决“最大子序列的分数”这一问题。核心思路在于排序 nums2
来优先选择最大乘数,然后通过维护 nums1
中最大和的 k
个数来最大化分数。希望这篇文章能够帮助你深入理解该题目的优化方法和代码实现。
原文地址:https://blog.csdn.net/qq_22841387/article/details/142729109
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!