2024-11-13：求出所有子序列的能量和。用go语言，给定一个整数数组nums和一个正整数k，定义一个子序列的能量为子序列

福大大架构师每日一题

发布于 2024-11-14 17:51:39

710

文章被收录于专栏：福大大架构师每日一题

2024-11-13：求出所有子序列的能量和。用go语言，给定一个整数数组nums和一个正整数k，

定义一个子序列的能量为子序列中任意两个元素之间的差值绝对值的最小值。

找出nums中长度为k的所有子序列的能量和，

对结果取模10^9 + 7后返回。

输入：nums = [1,2,3,4], k = 3。

输出：4。

解释：

nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。

答案2024-11-13：

chatgpt

题目来自leetcode3098。

大体步骤如下：

1.输入解析：

• 输入一个整数数组 nums 和一个正整数 k。
• 例如：nums = [1, 2, 3, 4]，k = 3。

2.预处理：

• 对 nums 进行排序，以便更容易处理差值。
• 计算所有可能的差值 vals，即对于每一对 (nums[i], nums[j])（i > j），计算 nums[i] - nums[j]，并将这些差值存入 vals。
• 将一个无穷大值 inf 添加到 vals 中，确保后续处理边界情况。
• 对 vals 进行排序并去重，得到唯一的差值数组。

3.动态规划数组初始化：

• 初始化三维数组 d，其中 d[i][p][v] 表示考虑到第 i 个元素，长度为 p 的子序列中，最小差值为 vals[v] 的子序列个数。
• 初始化二维数组 border，其中 border[i][p] 表示考虑到第 i 个元素，长度为 p 的子序列中，当前处理到的 vals 数组的索引边界。
• 初始化二维数组 sum 和 suf，用于计算前缀和和后缀和，以便快速更新 d 数组。

4.动态规划填充：

• 遍历 nums 中的每个元素 nums[i]，并对于每个 j < i，计算 nums[i] - nums[j] 在 vals 中的位置 pos。
• 对于每个可能的子序列长度 p（从 1 到 k），更新 d, sum, suf, 和 border 数组。
• 这一步的核心是利用前缀和和后缀和快速更新 d 数组，以及利用 border 数组来避免重复计算。

5.结果计算：

• 遍历每个 d[i][k][v]，其中 i 是 nums 的索引，k 是子序列长度，v 是 vals 的索引。
• 计算每个 d[i][k][v] 对结果的贡献，即 vals[v] * d[i][k][v]，并累加到 res 中。
• 对 res 取模 10^9 + 7 后返回。

6.输出：

• 输出最终计算得到的 res。

时间复杂度：

• 排序 nums：O(n log n)
• 生成 vals 并排序去重：O(n^2 log n^2)（因为最多有 n(n-1)/2 个差值，但去重和排序的复杂度较高）
• 动态规划填充：O(n^2 k m)，其中 n 是 nums 的长度，k 是子序列长度，m 是 vals 的长度（去重后的差值个数）。
• 结果计算：O(n m)
• 总时间复杂度：由于 m 最多为 n^2，因此总时间复杂度为 O(n^4 k)，但在实际情况下，由于 vals 的去重，m 通常远小于 n^2。

空间复杂度：

• 三维数组 d：O(n k m)
• 二维数组 border, sum, suf：O(n k) 和 O(k m)
• 其他辅助数组和变量：O(n^2)（用于存储差值 vals）
• 总空间复杂度：O(n k m + n^2)，同样地，由于 m 通常远小于 n^2，实际空间使用会更少。

综上所述，尽管理论上的时间复杂度和空间复杂度较高，但由于 vals 的去重和排序效率，以及动态规划过程中的前缀和、后缀和优化，实际运行时的性能可能会更好。

Go完整代码如下：

package main

import(
"fmt"
"sort"
)

const mod =1e9+7
const inf =0x3f3f3f3f

func sumOfPowers(nums []int, k int)int{
    n :=len(nums)
    sort.Ints(nums)

var vals []int
for i :=0; i < n; i++{
for j :=0; j < i; j++{
            vals =append(vals, nums[i]-nums[j])
}
}
    vals =append(vals, inf)
    sort.Ints(vals)
    vals = unique(vals)

    d :=make([][][]int, n)
for i :=range d {
        d[i]=make([][]int, k+1)
for j :=range d[i]{
            d[i][j]=make([]int,len(vals))
}
}

    border :=make([][]int, n)
for i :=range border {
        border[i]=make([]int, k+1)
}

    sum :=make([][]int, k+1)
for i :=range sum {
        sum[i]=make([]int,len(vals))
}

    suf :=make([][]int, n)
for i :=range suf {
        suf[i]=make([]int, k+1)
}
for i :=0; i < n; i++{
for j :=0; j < i; j++{
            pos := sort.SearchInts(vals, nums[i]-nums[j])
for p :=1; p <= k; p++{
for border[j][p]< pos {
                    sum[p][border[j][p]]=(sum[p][border[j][p]]- suf[j][p]+ mod)% mod
                    sum[p][border[j][p]]=(sum[p][border[j][p]]+ d[j][p][border[j][p]])% mod
                    suf[j][p]=(suf[j][p]- d[j][p][border[j][p]]+ mod)% mod
                    border[j][p]++
                    sum[p][border[j][p]]=(sum[p][border[j][p]]+ suf[j][p])% mod
}
}
}

        d[i][1][len(vals)-1]=1
for p :=2; p <= k; p++{
for v :=0; v <len(vals); v++{
                d[i][p][v]= sum[p-1][v]
}
}
for p :=1; p <= k; p++{
for v :=0; v <len(vals); v++{
                suf[i][p]=(suf[i][p]+ d[i][p][v])% mod
}
            sum[p][0]=(sum[p][0]+ suf[i][p])% mod
}
}

    res :=0
for i :=0; i < n; i++{
for v :=0; v <len(vals); v++{
            res =(res +int(int64(vals[v])*int64(d[i][k][v])%mod))% mod
}
}
return res
}

func unique(arr []int)[]int{
iflen(arr)==0{
return arr
}
    result :=[]int{arr[0]}
for _, v :=range arr {
if v != result[len(result)-1]{
            result =append(result, v)
}
}
return result
}

func main(){
    nums :=[]int{1,2,3,4}
    k :=3
    fmt.Println(sumOfPowers(nums, k))
}

Rust完整代码如下：

use std::collections::HashSet;

const MOD:i32=1_000_000_007;
const INF:i32=0x3f3f3f3f;

fnsum_of_powers(nums:Vec<i32>, k:usize)->i32{
letn= nums.len();
letmut nums= nums;
    nums.sort();

letmut vals=Vec::new();
foriin0..n {
forjin0..i {
            vals.push(nums[i]- nums[j]);
}
}
    vals.push(INF);
    vals.sort();
    vals =unique(vals);

letmut d=vec![vec![vec![0; vals.len()]; k +1]; n];

letmut border=vec![vec![0; k +1]; n];
letmut sum=vec![vec![0; vals.len()]; k +1];
letmut suf=vec![vec![0; k +1]; n];

foriin0..n {
forjin0..i {
letpos=match vals.binary_search(&(nums[i]- nums[j])){
Ok(p)=> p,
Err(p)=> p,
};
forpin1..=k {
while border[j][p]< pos {
                    sum[p][border[j][p]]=
(sum[p][border[j][p]]- suf[j][p]+ MOD)% MOD;
                    sum[p][border[j][p]]=
(sum[p][border[j][p]]+ d[j][p][border[j][p]])% MOD;
                    suf[j][p]=(suf[j][p]- d[j][p][border[j][p]]+ MOD)% MOD;
                    border[j][p]+=1;
                    sum[p][border[j][p]]=
(sum[p][border[j][p]]+ suf[j][p])% MOD;
}
}
}

        d[i][1][vals.len()-1]=1;
forpin2..=k {
forvin0..vals.len(){
                d[i][p][v]= sum[p -1][v];
}
}
forpin1..=k {
forvin0..vals.len(){
                suf[i][p]=(suf[i][p]+ d[i][p][v])% MOD;
}
            sum[p][0]=(sum[p][0]+ suf[i][p])% MOD;
}
}

letmut res=0;
foriin0..n {
forvin0..vals.len(){
            res =(res + vals[v]asi64* d[i][k][v]asi64% MOD asi64)% MOD asi64;
}
}
    res asi32
}

fnunique(mut arr:Vec<i32>)->Vec<i32>{
if arr.is_empty(){
return arr;
}
    arr.sort();
letmut result=Vec::new();
letmut prev= arr[0];
    result.push(prev);
for&v in&arr[1..]{
if v != prev {
            result.push(v);
            prev = v;
}
}
    result
}

fnmain(){
letnums=vec![1,2,3,4];
letk=3;
println!("{}",sum_of_powers(nums, k));
}