2023-04-19：给定一个非负数组arr
任何两个数差值的绝对值，如果arr中没有，都要加入到arr里
然后新的arr继续，任何两个数差值的绝对值，如果arr中没有，都要加入到arr里
一直到arr大小固定。
请问最终arr长度是多少。
1 <= arr的长度 <= 10^5
0 <= arr的数值 <= 10^5
来自国外题目论坛。

答案2023-04-19：

暴力方法

我们可以先从暴力方法考虑，逐步计算每一轮得到的新的 arr。具体来说，我们可以用一个列表 list 来记录每一轮的 arr，用一个 set 来记录 arr 中已有的数值。对于每一轮，我们遍历 list 中的所有元素，把它们之间的差值（绝对值）加入到 set 中，如果这个差值不在 set 中，则将其加入到 list 和 set 中。重复进行此操作，直到 list 不再发生变化为止，此时 list 的长度即为最终 arr 的长度。

时间复杂度：O(n ^ 2)，其中 n 是 arr 的长度。因为在每一轮中，我们需要遍历 list 中的所有元素，所以总共的时间复杂度是 O(n ^ 2)。

空间复杂度为 O(n)。

正式方法

上面的暴力方法时间复杂度较高，我们可以试着寻找更优的解法。

我们首先观察题目，发现每次增加的差值都是 arr 中已有的数值之间的差值，因此我们可以考虑对 arr 中的数值进行拆分，把每个数值拆成其所有可能的因子。例如，如果 arr 中有一个数值 num=20，则它的因子包括 1、2、4、5、10 和 20，我们可以将这些因子都加入到一个新的列表 factors 中。

接下来，我们可以根据 factors 中的元素计算出所有可能的差值，并放入到一个新的列表 diffs 中。注意，为了避免重复计算，我们只需要计算 diffs 中不存在的差值即可。

最后，我们可以将 diffs 中的元素加入到 arr 中，并对 arr 进行去重操作。如果 arr 不再发生变化，说明 arr 的长度已经固定，此时 arr 的长度即为最终结果。

时间复杂度：O(n log n)，其中 n 是 arr 的长度。首先，我们需要对每个数值进行因子分解，这一步的时间复杂度是 O(n log n)。然后，我们需要计算所有可能的差值，在 diffs 中去重，这一步的时间复杂度也是 O(n log n)。因此，总共的时间复杂度是 O(n log n)。

空间复杂度为 O(nlogn)。

golang完整代码

package main

import (
    "fmt"
    "math/rand"
    "time"
)

// 暴力方法
// 为了验证
func finalLen1(arr []int) int {
    list := make([]int, len(arr))
    copy(list, arr)
    set := make(map[int]bool)
    for _, num := range arr {
        set[num] = true
    }
    for !finish(&list, set) {
    }
    return len(list)
}

func finish(list *[]int, set map[int]bool) bool {
    len := len(*list)
    modified := false
    for i := 0; i < len; i++ {
        for j := i + 1; j < len; j++ {
            abs := (*list)[i] - (*list)[j]
            if abs < 0 {
                abs = -abs
            }
            if !set[abs] {
                *list = append(*list, abs)
                set[abs] = true
                modified = true
            }
        }
    }
    return !modified
}

// 正式方法
// 时间复杂O(N)
func finalLen2(arr []int) int {
    max := 0
    // 任意一个非0的值
    gcd := 0
    counts := make(map[int]int)
    for _, num := range arr {
        if num > max {
            max = num
        }
        if num != 0 {
            gcd = num
        }
        counts[num]++
    }
    if gcd == 0 { // 数组中都是0
        return len(arr)
    }
    // 不都是0
    for _, num := range arr {
        if num != 0 {
            gcd = Gcd(gcd, num)
        }
    }
    // max / gcd
    ans := max / gcd
    ans += counts[0]

    add := false
    for key, value := range counts {
        if key != 0 {
            ans += value - 1
        }
        if !add && value > 1 && counts[0] == 0 {
            ans++
            add = true
        }
    }
    return ans
}

// O(1)
func Gcd(m int, n int) int {
    if n == 0 {
        return m
    }
    return Gcd(n, m%n)
}

// 为了测试
func randomArray(n int, v int) []int {
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        ans[i] = rand.Intn(v)
    }
    return ans
}

// 为了测试
func main() {
    rand.Seed(time.Now().Unix())
    N := 15
    V := 50
    testTime := 8000
    fmt.Println("功能测试开始")
    for i := 0; i < testTime; i++ {
        n := rand.Intn(N) + 1
        arr := randomArray(n, V)
        ans1 := finalLen1(arr)
        ans2 := finalLen2(arr)
        if ans1 != ans2 {
            fmt.Printf("%v 出错了!\n", arr)
        }
    }
    fmt.Println("功能测试结束")
}

rust完整代码

use rand::Rng;
use std::collections::HashMap;

// 为了验证，不是正式方法
fn final_len_1(arr: &Vec<i32>) -> i32 {
    let mut list: Vec<i32> = vec![];
    let mut set: HashMap<i32, bool> = HashMap::new();
    for &num in arr {
        list.push(num);
        set.insert(num, true);
    }
    while !finish(&mut list, &mut set) {}
    return list.len() as i32;
}

// 为了验证
fn finish(list: &mut Vec<i32>, set: &mut HashMap<i32, bool>) -> bool {
    let len = list.len();
    let mut modified = false;
    for i in 0..len {
        for j in (i + 1)..len {
            let abs = (list[i] - list[j]).abs();
            if !set.contains_key(&abs) {
                list.push(abs);
                set.insert(abs, true);
                modified = true;
            }
        }
    }
    return !modified;
}

// 正式方法
// 时间复杂度O(N)
fn final_len_2(arr: &Vec<i32>) -> i32 {
    let mut max = 0;
    // 任意一个非0的值
    let mut gcd_value = 0;
    let mut counts: HashMap<i32, i32> = HashMap::new();
    for &num in arr {
        max = max.max(num);
        if num != 0 {
            gcd_value = num;
        }
        *counts.entry(num).or_insert(0) += 1;
    }

    if gcd_value == 0 {
        return arr.len() as i32;
    }

    // 不都是0
    for &num in arr {
        if num != 0 {
            gcd_value = gcd(gcd_value, num);
        }
    }

    // max / gcd
    let mut ans = max / gcd_value;
    ans += *counts.get(&0).unwrap_or(&0);

    let mut add = false;
    for (&key, &value) in counts.iter() {
        if key != 0 {
            ans += value - 1;
        }

        if !add && value > 1 && !counts.contains_key(&0) {
            ans += 1;
            add = true;
        }
    }

    return ans;
}

// O(1)
fn gcd(m: i32, n: i32) -> i32 {
    if n == 0 {
        return m;
    }
    return gcd(n, m % n);
}

// 为了测试
fn random_array(n: usize, v: i32) -> Vec<i32> {
    let mut ans: Vec<i32> = vec![];
    let mut rng = rand::thread_rng(); // 随机数生成器
    for _i in 0..n {
        ans.push(rng.gen_range(0, v));
    }
    return ans;
}

// 为了测试
fn main() {
    let n = 15;
    let v = 50;
    let test_time = 8000;

    println!("功能测试开始");
    for _i in 0..test_time {
        let len = (rand::random::<usize>() % n) + 1;
        let arr = random_array(len, v);
        let ans1 = final_len_1(&arr);
        let ans2 = final_len_2(&arr);
        if ans1 != ans2 {
            print!("出错：");
            for &num in arr.iter() {
                print!("{} ", num);
            }
            println!();
        }
    }
    println!("功能测试结束");
}

本作品采用《CC 协议》，转载必须注明作者和本文链接