贪心题目：和有限的最长子序列

文章目录题目标题和出处难度题目描述要求示例数据范围解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目标题和出处标题和有限的最长子序列出处2389. 和有限的最长子序列难度2 级题目描述要求给定一个长度为n \texttt{n}n的整数数组nums \texttt{nums}nums和一个长度为m \texttt{m}m的整数数组queries \texttt{queries}queries。返回一个长度为m \texttt{m}m的数组answer \texttt{answer}answer其中answer[i] \texttt{answer[i]}answer[i]是nums \texttt{nums}nums中元素之和小于等于queries[i] \texttt{queries[i]}queries[i]的子序列的最大长度。子序列是由一个数组删除某些元素或不删除元素且不改变剩余元素顺序得到的数组。示例示例 1输入nums [4,5,2,1], queries [3,10,21] \texttt{nums [4,5,2,1], queries [3,10,21]}nums [4,5,2,1], queries [3,10,21]输出[2,3,4] \texttt{[2,3,4]}[2,3,4]解释查询的回答如下子序列[2,1] \texttt{[2,1]}[2,1]的和小于或等于3 \texttt{3}3。可以证明满足题目要求的子序列的最大长度是2 \texttt{2}2所以answer[0] 2 \texttt{answer[0] 2}answer[0] 2。子序列[4,5,1] \texttt{[4,5,1]}[4,5,1]的和小于或等于10 \texttt{10}10。可以证明满足题目要求的子序列的最大长度是3 \texttt{3}3所以answer[1] 3 \texttt{answer[1] 3}answer[1] 3。子序列[4,5,2,1] \texttt{[4,5,2,1]}[4,5,2,1]的和小于或等于21 \texttt{21}21。可以证明满足题目要求的子序列的最大长度是4 \texttt{4}4所以answer[2] 4 \texttt{answer[2] 4}answer[2] 4。示例 2输入nums [2,3,4,5], queries [1] \texttt{nums [2,3,4,5], queries [1]}nums [2,3,4,5], queries [1]输出[0] \texttt{[0]}[0]解释空子序列是唯一一个满足元素和小于或等于1 \texttt{1}1的子序列所以answer[0] 0 \texttt{answer[0] 0}answer[0] 0。数据范围n nums.length \texttt{n} \texttt{nums.length}nnums.lengthm queries.length \texttt{m} \texttt{queries.length}mqueries.length1 ≤ n, m ≤ 1000 \texttt{1} \le \texttt{n, m} \le \texttt{1000}1≤n, m≤10001 ≤ nums[i], queries[i] ≤ 10 6 \texttt{1} \le \texttt{nums[i], queries[i]} \le \texttt{10}^\texttt{6}1≤nums[i], queries[i]≤106解法一思路和算法这道题要求对于每个查询找到数组nums \textit{nums}nums中的元素之和小于等于查询值的最大元素个数。数组中的元素都是正整数在元素综合不超过查询值的情况下为了使元素个数最多应选取最小的元素理由如下。用query \textit{query}query表示查询值。假设选取最小的元素时最多可以选取size \textit{size}size个元素元素之和为sum \textit{sum}sum则sum ≤ query \textit{sum} \le \textit{query}sum≤query且再多选取任意一个元素都会使元素之和超过query \textit{query}query。用sum ′ \textit{sum}sum′表示最小的size 1 \textit{size} 1size1个元素之和则sum ′ query \textit{sum} \textit{query}sum′query。将最小的size 1 \textit{size} 1size1个元素中的任意一个元素替换成更大的元素替换之后的size 1 \textit{size} 1size1个元素之和大于sum ′ \textit{sum}sum′因此大于query \textit{query}query。因此不可能选取size 1 \textit{size} 1size1个元素使元素之和不超过query \textit{query}query该查询的答案为size \textit{size}size。根据上述分析可以使用贪心的思想计算每个查询的答案。由于元素之和与元素顺序无关因此可以将数组nums \textit{nums}nums按升序排序然后对于每个查询找到nums \textit{nums}nums的元素之和小于等于查询值的最长前缀该前缀长度即为查询的答案。代码classSolution{publicint[]answerQueries(int[]nums,int[]queries){Arrays.sort(nums);intnnums.length,mqueries.length;int[]answernewint[m];for(inti0;im;i){intqueryqueries[i];intsize0;intsum0;for(intj0;jn;j){if(sumnums[j]query){break;}sumnums[j];size;}answer[i]size;}returnanswer;}}复杂度分析时间复杂度O ( n log ⁡ n n m ) O(n \log n nm)O(nlognnm)其中n nn是数组nums \textit{nums}nums的长度m mm是数组queries \textit{queries}queries的长度。排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间有m mm个查询每个查询需要O ( n ) O(n)O(n)的时间因此时间复杂度是O ( n log ⁡ n n m ) O(n \log n nm)O(nlognnm)。空间复杂度O ( log ⁡ n ) O(\log n)O(logn)其中n nn是数组nums \textit{nums}nums的长度。排序需要O ( log ⁡ n ) O(\log n)O(logn)的递归调用栈空间。注意返回值不计入空间复杂度。解法二思路和算法将数组nums \textit{nums}nums按升序排序之后由于每次查询都需要找到nums \textit{nums}nums的元素之和小于等于查询值的最长前缀且元素都是正整数因此nums \textit{nums}nums的前缀和数组为单调递增可以在前缀和数组中使用二分查找得到每个查询的答案。创建长度为n 1 n 1n1的前缀和数组prefixSums \textit{prefixSums}prefixSums其中prefixSums [ 0 ] 0 \textit{prefixSums}[0] 0prefixSums[0]0对于0 ≤ i n 0 \le i n0≤in有prefixSums [ i 1 ] prefixSums [ i ] nums [ i ] \textit{prefixSums}[i 1] \textit{prefixSums}[i] \textit{nums}[i]prefixSums[i1]prefixSums[i]nums[i]此时nums \textit{nums}nums已经按升序排序即prefixSums [ i ] \textit{prefixSums}[i]prefixSums[i]表示nums \textit{nums}nums的长度为i ii的前缀的元素之和。对于查询值query \textit{query}query找到满足prefixSums [ index ] ≤ query \textit{prefixSums}[\textit{index}] \le \textit{query}prefixSums[index]≤query的最大下标index \textit{index}index则查询的答案为index \textit{index}index。代码classSolution{publicint[]answerQueries(int[]nums,int[]queries){Arrays.sort(nums);intnnums.length,mqueries.length;int[]prefixSumsnewint[n1];for(inti0;in;i){prefixSums[i1]prefixSums[i]nums[i];}int[]answernewint[m];for(inti0;im;i){answer[i]binarySearch(prefixSums,queries[i]);}returnanswer;}publicintbinarySearch(int[]prefixSums,inttarget){intlow-1,highprefixSums.length-1;while(lowhigh){intmidlow(high-low1)/2;if(prefixSums[mid]target){lowmid;}else{highmid-1;}}returnlow;}}复杂度分析时间复杂度O ( n log ⁡ n m log ⁡ n ) O(n \log n m \log n)O(nlognmlogn)其中n nn是数组nums \textit{nums}nums的长度m mm是数组queries \textit{queries}queries的长度。排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间计算前缀和数组需要O ( n ) O(n)O(n)的时间有m mm个查询每个查询使用二分查找需要O ( log ⁡ n ) O(\log n)O(logn)的时间因此时间复杂度是O ( n log ⁡ n m log ⁡ n ) O(n \log n m \log n)O(nlognmlogn)。空间复杂度O ( n ) O(n)O(n)其中n nn是数组nums \textit{nums}nums的长度。排序需要O ( log ⁡ n ) O(\log n)O(logn)的递归调用栈空间排序后需要创建长度为n 1 n 1n1的前缀和数组因此空间复杂度是O ( n ) O(n)O(n)。注意返回值不计入空间复杂度。