2023-04-19：给定一个非负数组 arr 任何两个数差值的绝对值，如果 arr 中没有，都要加入到 arr 里然后新的 arr 继续，任何两个数差值的绝对值，如果 arr 中没有，都要加入到 arr 里一直到 arr 大小固定。请问最终 arr 长度是多少。1 <= arr 的长度 <= 10^50 <= 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!("功能测试结束");}
复制代码
评论