2023-04-29：一個序列的 寬度 定義為該序列中最大元素和最小元素的差值。 給你一個整
2023-04-29：一個序列的 寬度 定義為該序列中最大元素和最小元素的差值。給你一個整數(shù)數(shù)組 nums ，返回 nums 的所有非空 子序列 的 寬度之和 由于答案可能非常大，請返回對 109 + 7 取余 后的結(jié)果。子序列 定義為從一個數(shù)組里刪除一些（或者不刪除）元素， 但不改變剩下元素的順序得到的數(shù)組 例如，[3,6,2,7] 就是數(shù)組 [0,3,1,6,2,2,7] 的一個子序列。輸入：nums = [2,1,3]。輸出：6。
答案2023-04-29：
解題思路：
1.?排序
首先對數(shù)組進行排序，這樣我們就可以根據(jù)每個子序列的首尾元素來計算它的寬度了。
1.?計算寬度
我們使用 A 表示當前子序列的寬度，即末尾元素與首元素的差值，使用 B 表示上一個子序列的寬度，即前一次循環(huán)中的 A 值。具體計算過程如下：
A?=?(D?*?nums[i])?%?mod
B?=?((B?*?2)?%?mod?+?nums[i?-?1])?%?mod
ans?=?(ans?+?A?-?B?+?mod)?%?mod
C?=?(C?*?2)?%?mod
D?=?(D?+?C)?%?mod
其中 D 和 C 分別表示當前子序列的長度和可能的貢獻值，計算方法如下：
C?=?(C?*?2)?%?mod
D?=?(D?+?C)?%?mod
1.?取模
由于答案非常大，需要對其進行 10^9+7 取模，即將 ans 的值對 mod 取余。
時間復雜度：
排序的時間復雜度為 O(nlogn)，計算寬度的時間復雜度為 O(n)，因此總的時間復雜度為 O(nlogn)。
空間復雜度：
除了輸入數(shù)據(jù)外，算法使用了常數(shù)級別的額外空間，因此空間復雜度為 O(1)。
go完整代碼如下：
package?main
import?(
????"fmt"
????"sort"
)
func?sumSubseqWidths(nums?[]int)?int?{
????sort.Ints(nums)
????mod?:=?1000000007
????ans?:=?0
????var?A,?B,?C,?D?int64?=?0,?0,?1,?1
????for?i?:=?1;?i?<?len(nums);?i++?{
????????A?=?(D?*?int64(nums[i]))?%?int64(mod)
????????B?=?((B*2)%int64(mod)?+?int64(nums[i-1]))?%?int64(mod)
????????ans?=?(ans?+?int(A-B+int64(mod)))?%?int(mod)
????????C?=?(C?*?2)?%?int64(mod)
????????D?=?(D?+?C)?%?int64(mod)
????}
????return?ans
}
func?main()?{
????nums?:=?[]int{2,?1,?3}
????result?:=?sumSubseqWidths(nums)
????fmt.Println(result)
}
rust完整代碼如下：
fn?sum_subseq_widths(nums:?Vec<i32>)?->?i32?{
????let?mut?nums?=?nums.clone();
????nums.sort_unstable();
????let?mod_num?=?1000000007;
????let?mut?ans?=?0;
????let?mut?a?=?0;
????let?mut?b?=?0;
????let?mut?c?=?1;
????let?mut?d?=?1;
????for?i?in?1..nums.len()?{
????????a?=?(d?*?nums[i]?as?i64)?%?mod_num;
????????b?=?((b?*?2)?%?mod_num?+?nums[i?-?1]?as?i64)?%?mod_num;
????????ans?=?(ans?+?a?-?b?+?mod_num)?%?mod_num;
????????c?=?(c?*?2)?%?mod_num;
????????d?=?(d?+?c)?%?mod_num;
????}
????ans?as?i32
}
fn?main()?{
????let?nums?=?vec![2,?1,?3];
????let?result?=?sum_subseq_widths(nums);
????println!("{}",?result);?
}
c完整代碼如下：
#include?<stdio.h>
#include?<stdlib.h>
#include?<string.h>
#define?MOD?1000000007
int?compare(const?void*?a,?const?void*?b)?{
????return?*(int*)a?-?*(int*)b;
}
int?sumSubseqWidths(int*?nums,?int?numsSize)?{
????qsort(nums,?numsSize,?sizeof(int),?compare);
????long?ans?=?0,?A?=?0,?B?=?0,?C?=?1,?D?=?C;
????for?(int?i?=?1;?i?<?numsSize;?i++)?{
????????A?=?(D?*?nums[i])?%?MOD;
????????B?=?((B?*?2)?%?MOD?+?nums[i?-?1])?%?MOD;
????????ans?=?(ans?+?A?-?B?+?MOD)?%?MOD;
????????C?=?(C?*?2)?%?MOD;
????????D?=?(D?+?C)?%?MOD;
????}
????return?(int)ans;
}
int?main()?{
????int?nums[]?=?{?2,?1,?3?};
????int?numsSize?=?sizeof(nums)?/?sizeof(nums[0]);
????int?result?=?sumSubseqWidths(nums,?numsSize);
????printf("%d\n",?result);?
????return?0;
}
c++完整代碼如下：
#include?<iostream>
#include?<vector>
#include?<algorithm>
using?namespace?std;
int?sumSubseqWidths(vector<int>&?nums)?{
????sort(nums.begin(),?nums.end());
????const?int?mod?=?1000000007;
????long?ans?=?0,?A?=?0,?B?=?0,?C?=?1,?D?=?C;
????for?(int?i?=?1;?i?<?nums.size();?i++)?{
????????A?=?(D?*?nums[i])?%?mod;
????????B?=?((B?*?2)?%?mod?+?nums[i?-?1])?%?mod;
????????ans?=?(ans?+?A?-?B?+?mod)?%?mod;
????????C?=?(C?*?2)?%?mod;
????????D?=?(D?+?C)?%?mod;
????}
????return?static_cast<int>(ans);
}
int?main()?{
????vector<int>?nums{?2,?1,?3?};
????int?result?=?sumSubseqWidths(nums);
????cout?<<?result?<<?endl;?//?輸出：6
????return?0;
}
