英雄力量【LC2681】
给你一个下标从 0 开始的整数数组
nums，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：
i0，i1，…ik表示这组英雄在数组中的下标。那么这组英雄的力量为max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik])。请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对
109 + 7取余。
妙哉
-
思路
-
对于子序列而言，数组元素顺序不影响结果，因此先将数组排序
-
枚举每个元素作为子序列的最小值，那么元素 n u m s [ i ] nums[i] nums[i]作为最小值的子序列的贡献为
n u m s [ i ] ∗ ( n u m s [ i ] 2 + n u m s [ i + 1 ] 2 + 2 ∗ n u m s [ i + 2 ] 2 . . . + 2 n − i − 2 ∗ n u m s [ n − 1 ] ) = n u m s [ i ] 3 + n u m s [ i ] ∗ ( n u m s [ i + 1 ] 2 + 2 ∗ n u m s [ i + 2 ] 2 . . . + 2 n − i − 2 ∗ n u m s [ n − 1 ] ) = n u m s [ i ] 3 + p nums[i]*(nums[i]^2+nums[i+1]^2+2*nums[i+2]^2 ...+2^{n-i-2}*nums[n-1])\\ =nums[i]^3+nums[i]*(nums[i+1]^2+2*nums[i+2]^2 ...+2^{n-i-2}*nums[n-1])\\ =nums[i]^3+p nums[i]∗(nums[i]2+nums[i+1]2+2∗nums[i+2]2...+2n−i−2∗nums[n−1])=nums[i]3+nums[i]∗(nums[i+1]2+2∗nums[i+2]2...+2n−i−2∗nums[n−1])=nums[i]3+p -
实现时从右往左枚举左小指，先将 n u m s [ i ] 3 nums[i]^3 nums[i]3累加至结果，然后维护变量 p p p，每次将 n u m s [ i ] ∗ p nums[i]*p nums[i]∗p累加至结果，再令 p = p ∗ 2 + n u m s [ i ] 2 p= p *2+nums[i]^2 p=p∗2+nums[i]2文章来源：https://www.toymoban.com/news/detail-621692.html
-
-
实现文章来源地址https://www.toymoban.com/news/detail-621692.html
class Solution { public int sumOfPower(int[] nums) { final int mod = (int) 1e9 + 7; Arrays.sort(nums); long ans = 0, p = 0; for (int i = nums.length - 1; i >= 0; --i) { long x = nums[i]; ans = (ans + (x * x % mod) * x) % mod; ans = (ans + x * p % mod) % mod; p = (p * 2 + x * x % mod) % mod; } return (int) ans; } } 作者：ylb 链接：https://leetcode.cn/problems/power-of-heroes/solutions/2367175/python3javacgotypescript-yi-ti-yi-jie-pa-lgos/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。- 复杂度
- 时间复杂度： O ( log n ) \mathcal{O}(\log n) O(logn)
- 空间复杂度： O ( n log n ) \mathcal{O}(n \log n) O(nlogn)
- 复杂度
到了这里，关于【每日一题Day282】LC2681英雄力量 | 排序+数学的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
