【每日一题Day282】LC2681英雄力量 | 排序+数学

英雄力量【LC2681】

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：

i0 ，i1 ，… ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 109 + 7 取余。

妙哉

• 思路

• 对于子序列而言，数组元素顺序不影响结果，因此先将数组排序
  
• 枚举每个元素作为子序列的最小值，那么元素nums[i]作为最小值的子序列的贡献为
• 实现时从右往左枚举左小指，先将nums[i]3累加至结果，然后维护变量p，每次将nums[i]∗p累加至结果，再令p=p∗2+nums[i]2

• 实现

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 )

空间复杂度：O ( n log n )

————————————————

版权声明：本文为CSDN博主「TIkitianya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/Tikitian/article/details/132036644