891. Sum of Subsequence Widths
难度: Hard
刷题内容
原题连接
- https://leetcode.com/problems/sum-of-subsequence-widths
内容描述
Given an array of integers A, consider all non-empty subsequences of A.
For any sequence S, let the width of S be the difference between the maximum and minimum element of S.
Return the sum of the widths of all subsequences of A.
As the answer may be very large, return the answer modulo 10^9 + 7.
Example 1:
Input: [2,1,3]
Output: 6
Explanation:
Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.
Note:
1 <= A.length <= 20000
1 <= A[i] <= 20000
解题方案
思路 1 **- 时间复杂度: O(NlgN)*- 空间复杂度: O(N)***
- 我们逆向思路解决这个问题。结果要求最大数减去最小数的差之和，我们可以认为是，把所有的子序列的最大值累加，减去所有的子序列的最小值的累加值
- 数组中最大数，在子数组中也是最大数的，有2^(n-1)个子数组，同理，第二大数，在子数组是最大数的，有2^(n-2)个子数组，以此类推
- 同理，最小数也是这样计算
- 复杂度是O(nlgn)
代码：
class Solution {
private static int MOD = 1000000007;
private static int[] pow2;
private void init() {
if (pow2 == null) {
pow2 = new int[20000];
pow2[0] = 1;
for (int i = 1;i < pow2.length;i++) {
pow2[i] = pow2[i - 1] * 2;
if (pow2[i] >= MOD) {
pow2[i] -= MOD;
}
}
}
}
public int sumSubseqWidths(int[] A) {
init();
Arrays.sort(A);
int ret = 0;
for (int i = 0;i < A.length;i++) {
ret += (long)A[i] * pow2[i] % MOD;
if (ret >= MOD) {
ret -= MOD;
}
ret -= (long)A[i] * pow2[A.length - i - 1] % MOD;
if (ret < 0) {
ret += MOD;
}
}
return ret;
}
}
