力扣(LeetCode)891. 子序列宽度之和C++)

数学推理

贡献法

由题意可知，子序列的内部顺序不影响宽度，所以可以对子序列排序。得到正序序列。
如 $123456$ ， 序列中数字 $4$ 的下标 $i=3$ ，对于数字 $4$ ， 最大值为 $4$ 的子序列个数为 $2^3=2^i$ ， 最大值 $4$ 左侧数可选可不选，每个数有选或不选 $2$ 种情况，一共 $3$ 个数 ， 对应 $2^3=2^i=8$ 种状态。

或者用组合的形式理解， 最大值$4$ 固定，而前面有 $3$ 个数，一共有 $C_3^0+C_3^1+C_3^2+C_3^3=2^3$ 种状态。推广到 $i$ 个数，有 $C_i^0+C_i^1+\dots C_i^i=2^i$ 种状态。

同理，以 $4$ 为最小值的子序列有 $2^{n-1-i}$ 个，$n$ 是数字总数 ，$i$ 是数字下标。

数字 $x$ 对答案的贡献 $=2^i\times x-2^{n-1-i}\times x=(2^i-2^{n-1-i})\times x$。
统计所有数对答案的贡献，即为所求。

预处理2的幂

class Solution {
private:
    const int mod = 1e9 +7;
public:
    int sumSubseqWidths(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int pow2[n];
        pow2[0] = 1;
        for(int i = 1;i<n;i++) pow2[i] = (pow2[i-1]*2)%mod;//预处理2^i
        long long ans = 0;
        for(int i = 0;i<n;i++) ans =  (ans+(long long)(pow2[i]-pow2[n-1-i]) * nums[i]) % mod;
        return (ans+mod)%mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度 $O(nlogn)$ ， 时间瓶颈在于排序。预处理 $2$ 的幂的时间复杂度 $O(n)$，遍历所有数的时间复杂度 $O(n)$ ， 总时间复杂度 $O(nlogn+2n)$。

空间复杂度 $O(n)$ 预处理2的幂使用了数组存储, 空间复杂度 $O(n)$ , 快排的空间复杂度 $O(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<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        long long ans = 0;
        for(int i = 0;i<n;i++) ans =  (ans+(qmi(2,i,mod)-qmi(2,n-1-i,mod))*nums[i]) % mod;
        return (ans%mod+mod)%mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度 $O(nlogn)$ ，排序的时间复杂度 $O(nlogn)$，遍历所有数的时间复杂度 $O(n)$，求快速幂的时间复杂度 $O(logn)$ ， 遍历的同时使用快速幂时间复杂度 $O(logn)$ ， 总时间复杂度 $O(3\times nlogn)$。

空间复杂度 $O(logn)$ 快排的空间复杂度 $O(logn)$。

转换思路

对上述思想，转换思路，得
$2^i$ 对答案的贡献为 $2^i\times (nums[i]-nums[n-1-i])$

class Solution {
private:
    const int mod = 1e9 +7;
public:
    int sumSubseqWidths(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        long long ans = 0;
        long long pow2 = 1;
        for(int i = 0;i<n;i++){
            ans = (ans+(long long)pow2*(nums[i] - nums[n-1-i])%mod) %mod;
            pow2 = (pow2<<1)%mod;
        }
        return (ans%mod+mod)%mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

读者可以想想转换思路的妙处。

时间复杂度 $O(nlogn)$ ， 时间瓶颈在于排序。遍历所有数的时间复杂度 $O(n)$ ， 总时间复杂度 $O(nlogn+n)$。

空间复杂度 $O(logn)$ 快排的空间复杂度 $O(logn)$。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC