写点什么

2023-04-29:一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。 给你一个整数数组 nums ,返回 nums 的所有非空 子序列 的 宽度之和 由于答案可能非常大,请返回对 109

  • 2023-04-29
    北京
  • 本文字数:1842 字

    阅读完需:约 6 分钟

2023-04-29:一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。给你一个整数数组 nums ,返回 nums 的所有非空 子序列 的 宽度之和由于答案可能非常大,请返回对 109 + 7 取余 后的结果。子序列 定义为从一个数组里删除一些(或者不删除)元素,但不改变剩下元素的顺序得到的数组例如,[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。输入:nums = [2,1,3]。输出:6。


答案 2023-04-29:

解题思路:

  1. 排序


首先对数组进行排序,这样我们就可以根据每个子序列的首尾元素来计算它的宽度了。


  1. 计算宽度


我们使用 A 表示当前子序列的宽度,即末尾元素与首元素的差值,使用 B 表示上一个子序列的宽度,即前一次循环中的 A 值。具体计算过程如下:


A = (D * nums[i]) % modB = ((B * 2) % mod + nums[i - 1]) % modans = (ans + A - B + mod) % modC = (C * 2) % modD = (D + C) % mod
复制代码


其中 D 和 C 分别表示当前子序列的长度和可能的贡献值,计算方法如下:


C = (C * 2) % modD = (D + C) % mod
复制代码


  1. 取模


由于答案非常大,需要对其进行 10^9+7 取模,即将 ans 的值对 mod 取余。


时间复杂度:


排序的时间复杂度为 O(nlogn),计算宽度的时间复杂度为 O(n),因此总的时间复杂度为 O(nlogn)。


空间复杂度:


除了输入数据外,算法使用了常数级别的额外空间,因此空间复杂度为 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;}
复制代码



发布于: 刚刚阅读数: 3
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-04-29:一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。 给你一个整数数组 nums ,返回 nums 的所有非空 子序列 的 宽度之和 由于答案可能非常大,请返回对 109_golang_福大大架构师每日一题_InfoQ写作社区