LeetCode 0891. 子序列宽度之和
创始人
2024-01-29 14:23:23
0

【LetMeFly】891.子序列宽度之和

力扣题目链接:https://leetcode.cn/problems/sum-of-subsequence-widths/

一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 nums ,返回 nums 的所有非空 子序列宽度之和 。由于答案可能非常大,请返回对 109 + 7 取余 后的结果。

子序列 定义为从一个数组里删除一些(或者不删除)元素,但不改变剩下元素的顺序得到的数组。例如,[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。

 

示例 1:

输入:nums = [2,1,3]
输出:6
解释:子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。

示例 2:

输入:nums = [2]
输出:0

 

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

方法一:排序求贡献

本题只关注序列的最大值和最小值,同时,“序列”是不要求“连续”的

因此答案和数组中元素的顺序无关,我们可以对数组先排个序

排序之后,对于下标为iii的元素,以nums[i]nums[i]nums[i]为最值的子序列个数为2i2^i2i个(不考虑两个元素相等的情况),因此nums[i]nums[i]nums[i]对答案的贡献有2i×nums[i]2^i\times nums[i]2i×nums[i];以nums[i]nums[i]nums[i]为最值的子序列个数为2n−i−12^{n - i - 1}2n−i−1个,因此nums[i]nums[i]nums[i]对答案的贡献有−2n−i−1×nums[i]-2^{n - i - 1}\times nums[i]−2n−i−1×nums[i]

1 5 7 9↑下标为2以nums[2]为最大值的子序列有:[7], [1, 7], [5, 7], [1, 5, 7]共4个以nums[2]为最小值的子序列有:[7], [7, 9]共2个这里不需要考虑7计算两次的情况,因为单独一个[7]的“宽度”为0这里不需要考虑元素相等的情况。假如原数组为1, 7, 7, 9,那么计算结果是不受影响的

我们可以预处理求得2i2^i2i,也可以使用快速幂

  • 时间复杂度O(nlog⁡n)O(n\log n)O(nlogn),其中nnn是数组中原神的个数
  • 空间复杂度O(n)O(n)O(n)

AC代码

C++

typedef long long ll;
const ll MOD = 1e9 + 7;
class Solution {
public:int sumSubseqWidths(vector& nums) {sort(nums.begin(), nums.end());ll ans = 0;int n = nums.size();vector Pow(n);Pow[0] = 1;for (int i = 1; i < n; i++)Pow[i] = (Pow[i - 1] * 2) % MOD;for (int i = 0; i < n; i++) {ans = (ans + (Pow[i] - Pow[n - i - 1]) * nums[i]) % MOD;}return (ans % MOD + MOD) % MOD;}
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/127916253

相关内容

热门资讯

「创业史有感」 小说《创业史》... 「创业史有感」小说《创业史》读后感发布时间:2020-03-27顺利加盟网-创业史有感:小说《创业史...
吉水农民刘国富 返乡创业发展生... 央广网吉水10月2日消息(记者邓玉玲通讯员郭建华)种有500余亩双季水稻,养殖20余种禽畜,种植30...
十万块创业 十万块创业 十万块... 大城市十万块能创业吗?一线城市十万块创业能做什么?要说人生有多少翻身仗要打,不说那些不切实际的剧情,...
十万块钱能创业吗 【广州fc吧... 因为创业本身就是一个从无到有的过程,没有条件自己去创造条件,没有路就自己去开路,形形色色的困难都要创...
十万块创业能做什么 【广州fc... 随着现在社会的发展,越来越多的人都有了自己的汽车,所以洗车行业也非常有市场,现在很多人都有洗车的需求...
2016宠物店投资创业方案最新... 如果10年前你开一家宠物店,肯定会落下个不务正业的恶名;然而在10年后的北京市场上,大大小小的特色宠...
全球女性创业者大会 全球女性创... 2019全球女性创业者大会马云发表演讲令全场赞叹不已,那么马云到底说了什么?下面由小编与大家分享,希...
创业项目分析 创业项目分析 创... 「项目环境分析」如何对项目外部环境进行分析?爱问知识人发布时间:2020-03-29发布人:项目环境...
创业项目创业项目分析可行性分析... 作为投资决策前必不可少的关键环节,项目可行性分析报告是在前一阶段的项目建议书获得审批通过的基础上,主...
如何进行创业项目可行性分析? ... 能不能获得融资往往是一个企业能否继续走下去的关键。要想获得融资,创始人首先要把BP交给投资人。那么你...