珠海网站建设杰作,软件开发上海,c2c网站建站的标准,长春网站制作的公司哪家好题目 给你两个下标从 0 开始的整数数组 nums1 和 nums2 #xff0c;两者长度都是 n #xff0c;再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。 对于选择的下标 i0 #xff0c;i1 #xff0c;…#xff0c; ik - 1 #xff0c;你的 分数 …题目 给你两个下标从 0 开始的整数数组 nums1 和 nums2 两者长度都是 n 再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。 对于选择的下标 i0 i1 … ik - 1 你的 分数 定义如下 nums1 中下标对应元素求和乘以 nums2 中下标对应元素的 最小值 。 用公式表示 (nums1[i0] nums1[i1] … nums1[ik - 1]) * min(nums2[i0] , nums2[i1], … ,nums2[ik - 1]) 。 请你返回 最大 可能的分数。 一个数组的 子序列 下标是集合 {0, 1, …, n-1} 中删除若干元素得到的剩余集合也可以不删除任何元素。 一、代码实现贪心优先队列
import (container/heapsort
)func maxScore(nums1 []int, nums2 []int, k int) int64 {n : len(nums1)pairs : make([][]int, n)for i : 0; i n; i {pairs[i] []int{nums2[i], nums1[i]}}sort.Slice(pairs, func(i, j int) bool {return pairs[i][0] pairs[j][0]})h : minHeap{}heap.Init(h)total : 0maxScore : 0for _, pair : range pairs {num2, num1 : pair[0], pair[1]heap.Push(h, num1)total num1if h.Len() k {total - heap.Pop(h).(int)}if h.Len() k {current : total * num2if current maxScore {maxScore current}}}return int64(maxScore)
}type minHeap []intfunc (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] h[j] }
func (h minHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h append(*h, x.(int)) }
func (h *minHeap) Pop() interface{} {old : *hn : len(old)x : old[n-1]*h old[:n-1]return x
}二、算法分析
1. 核心思路
排序策略将元素按nums2的值降序排列确保每次处理当前可能的子序列最小值。贪心选择维护一个最小堆动态保留当前最大的k个nums1值。实时计算当堆满k个元素时立即计算当前可能的最大分数。
2. 关键步骤 数据预处理 将nums1和nums2的元素配对并按nums2降序排列。 堆维护过程 使用最小堆动态维护最大的k个nums1值。每当堆元素超过k时弹出最小值以保持堆大小。 分数计算 每次堆满k个元素时计算当前和与当前nums2最小值的乘积更新最大分数。
3. 复杂度
指标值说明时间复杂度O(n log n)排序主导时间复杂度空间复杂度O(n)存储排序后的元素对
三、图解示例 四、边界条件与扩展
1. 特殊场景验证
全相同元素当所有nums2值相同时正确选取最大的k个nums1值。k等于数组长度此时必须全选分数为总和乘以最小值。大数值测试验证算法在极大数值时的正确性。
2. 扩展应用
动态k值调整支持k值根据条件变化时快速重新计算。多维约束增加其他维度的限制条件进行筛选。分布式计算处理超大规模数据时分布式排序和堆维护。
3. 多语言实现
import java.util.*;public class Solution {public int maxScore(int[] nums1, int[] nums2, int k) {int n nums1.length;int[][] pairs new int[n][2];for (int i 0; i n; i) {pairs[i][0] nums2[i];pairs[i][1] nums1[i];}Arrays.sort(pairs, (a, b) - b[0] - a[0]);PriorityQueueInteger heap new PriorityQueue();long total 0;long maxScore 0;for (int[] pair : pairs) {int num2 pair[0];int num1 pair[1];heap.offer(num1);total num1;if (heap.size() k) {total - heap.poll();}if (heap.size() k) {maxScore Math.max(maxScore, total * num2);}}return (int) maxScore;}
}import heapqdef maxScore(nums1, nums2, k):# 将nums2和nums1的元素配对并按nums2的值降序排列pairs sorted(zip(nums2, nums1), keylambda x: -x[0])heap []total 0max_score 0for num2, num1 in pairs:# 将当前nums1的值加入堆heapq.heappush(heap, num1)total num1# 如果堆的大小超过k弹出最小的元素if len(heap) k:removed heapq.heappop(heap)total - removed# 当堆中恰好有k个元素时计算当前分数if len(heap) k:current_score total * num2if current_score max_score:max_score current_scorereturn max_score五、总结与优化
1. 算法对比
方法优势适用场景贪心优先队列时间效率高需要动态维护最大值暴力枚举实现简单小规模数据动态规划可处理复杂约束需要状态转移的情况
2. 工程优化
内存优化在原数组上操作减少内存消耗。并行排序使用多线程加速大规模数据排序。剪枝策略提前终止不可能产生更优解的分支。
3. 扩展方向
在线处理支持数据流动态添加元素。多目标优化同时考虑多个目标函数的最优解。近似算法针对超大数据设计近似解法。
