力扣(LeetCode)891. 子序列宽度之和C++)
数学推理
贡献法
由题意可知，子序列的内部顺序不影响宽度，所以可以对子序列排序。得到正序序列。
如 1234561~2~3~4~5~61 2 3 4 5 6 ， 序列中数字 444 的下标 i=3i=3i=3 ，对于数字 444 ， 最大值为 444 的子序列个数为 23=2i2^3 = 2^i23=2i ， 最大值 444 左侧数可选可不选，每个数有选或不选 222 种情况，一共 333 个数 ， 对应 23=2i=82^3 = 2^i=823=2i=8 种状态。
或者用组合的形式理解， 最大值444 固定，而前面有 333 个数，一共有 C30+C31+C32+C33=23C_3^0+C_3^1+C_3^2+C_3^3 = 2^3C30+C31+C32+C33=23 种状态。推广到 iii 个数，有 Ci0+Ci1+…Cii=2iC_i^0+C_i^1+\dots C_i^i = 2^iCi0+Ci1+…Cii=2i 种状态。
同理，以 444 为最小值的子序列有 2n−1−i2^{n-1-i}2n−1−i 个，nnn 是数字总数 ，iii 是数字下标。
数字 xxx 对答案的贡献 =2i×x−2n−1−i×x=(2i−2n−1−i)×x=2^i\times x - 2^{n-1-i}\times x = (2^i-2^{n-1-i})\times x=2i×x−2n−1−i×x=(2i−2n−1−i)×x。
统计所有数对答案的贡献，即为所求。
预处理2的幂
class Solution {
private:const int mod = 1e9 +7;
public:int sumSubseqWidths(vector& nums) {sort(nums.begin(),nums.end());int n = nums.size();int pow2[n];pow2[0] = 1;for(int i = 1;i 时间复杂度 O(nlogn)O(nlogn)O(nlogn) ， 时间瓶颈在于排序。预处理 222 的幂的时间复杂度 O(n)O(n)O(n)，遍历所有数的时间复杂度 O(n)O(n)O(n) ， 总时间复杂度 O(nlogn+2n)O(nlogn + 2n)O(nlogn+2n)。
空间复杂度 O(n)O(n)O(n) 预处理2的幂使用了数组存储, 空间复杂度 O(n)O(n)O(n) , 快排的空间复杂度 O(logn)O(logn)O(logn) , 总时间复杂度 O(n+logn)O(n+logn)O(n+logn)。。
快速幂
class Solution {
private:const int mod = 1e9 +7;
public:long long qmi(int a,int b ,int p){long long ans = 1;while(b){if(b&1) ans = ans*a%p;b>>=1;a = (long long)a*a%p;}return ans;}int sumSubseqWidths(vector& nums) {sort(nums.begin(),nums.end());int n = nums.size();long long ans = 0;for(int i = 0;i 时间复杂度 O(nlogn)O(nlogn)O(nlogn) ，排序的时间复杂度 O(nlogn)O(nlogn)O(nlogn)，遍历所有数的时间复杂度 O(n)O(n)O(n)，求快速幂的时间复杂度 O(logn)O(logn)O(logn) ， 遍历的同时使用快速幂时间复杂度 O(logn)O(logn)O(logn) ， 总时间复杂度 O(3×nlogn)O(3\times nlogn)O(3×nlogn)。
空间复杂度 O(logn)O(logn)O(logn) 快排的空间复杂度 O(logn)O(logn)O(logn)。
转换思路
对上述思想，转换思路，得
2i2^i2i 对答案的贡献为 2i×(nums[i]−nums[n−1−i])2^i\times (nums[i] - nums[n-1-i])2i×(nums[i]−nums[n−1−i])
class Solution {
private:const int mod = 1e9 +7;
public:int sumSubseqWidths(vector& nums) {sort(nums.begin(),nums.end());int n = nums.size();long long ans = 0;long long pow2 = 1;for(int i = 0;ians = (ans+(long long)pow2*(nums[i] - nums[n-1-i])%mod) %mod;pow2 = (pow2<<1)%mod;}return (ans%mod+mod)%mod;}
};
读者可以想想转换思路的妙处。
时间复杂度 O(nlogn)O(nlogn)O(nlogn) ， 时间瓶颈在于排序。遍历所有数的时间复杂度 O(n)O(n)O(n) ， 总时间复杂度 O(nlogn+n)O(nlogn + n)O(nlogn+n)。
空间复杂度 O(logn)O(logn)O(logn) 快排的空间复杂度 O(logn)O(logn)O(logn)。
博主致语
理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。
AC
