题目描述
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
题意:给定一个整数数组 A
,考虑 A
的所有非空子序列。
对于任意序列S
,设 S
的宽度是S
的最大元素和最小元素的差。
返回 A
的所有子序列的宽度之和。
由于答案可能非常大,请返回答案模 10^9+7
。
算法1
题解:我们首先将数组排好序,那么对于所有不相同的数字,我们分别求出小于该数字的数字个数,等于该数字的数字个数,大于该数字的数字个数分别为smaller,equal,larger
。那么对于当前这个数字val
,我们分别考虑他在多少个子序列中充当了最大元素和在多少个字序列中充当了最小元素。
如果val
是最大元素,那么我们可以在所以smaller
个小于val
的数字中选择零到smaller
个数字,在equal
个相等的数字中,选择1到equal
个。总共在(1 << smaller) * ((1 << equal) - 1)
个子序列中充当了最大值。同理,在(1 << larger) * ((1 << equal) - 1)
个子序列中充当了最小值。
所以该数字对答案的贡献就是$(2^{small} - 2^{larger}) * (2^{equal} - 1) * val$。
最后考虑到取模,我们将上述公式拆分开分别取模即可。
int sumSubseqWidths(vector<int>& A) {
int n = A.size(),mod = 1000000007;
long long res = 0;
vector<int> powof2(n + 1,1);
for(int i = 1 ; i <= n ; i ++)
powof2[i] = (2 * powof2[i - 1]) % mod;
sort(A.begin(),A.end());
for(int i = 0,j = i + 1; i < n ; i = j,j = i + 1)
{
while(j < n && A[j] == A[j - 1])
j ++;
int smaller = i,equal = j - i,larger = n - j;
//res += ((1 << small) - (1 << larger)) * ((1 << same) - 1) * nums[i];
res = (res + ((1ll * A[i] * ((0ll + powof2[smaller + equal] - powof2[larger + equal] - powof2[smaller] + powof2[larger] + 2 * mod) % mod)) % mod)) % mod ;
}
return res ;
}
确定了val在子数组中是最大或者最小后,为啥就可以直接计算了呀,题目问的不是求区间长度正好等于最大值和最小值之差的区间个数吗,这个条件是从哪里体现的呀