2026-08-18：得到目标点的最少代数。用go语言，你有若干个三维空间中的整数点，每个点由三个坐标 (x, y, z) 表示。初始时这些点构成第 0

2026-08-18：得到目标点的最少代数。用go语言，你有若干个三维空间中的整数点，每个点由三个坐标 (x, y, z) 表示。初始时这些点构成第 0 代。

之后每一代，你从所有已经存在的点中，选择两个不同的点（坐标不能完全相同），计算它们坐标的平均值，并对每个坐标分别向下取整，得到一个新点。这些新点共同组成新一代。

所有新点是在同一时间生成的，并且生成后立即可以被用于后续的生成过程。

现在给定一个目标点，问最早在哪一代会出现这个目标点。如果它一开始就存在，返回 0；如果永远无法生成，返回 -1。

1 <= points.length <= 20。

points[i] = [xi, yi, zi]。

0 <= xi, yi, zi <= 6。

target.length == 3。

0 <= target[i] <= 6。

初始点集合不包含重复项。

输入： points = [[0,0,0],[6,6,6]], target = [3,3,3]。

输出： 1。

解释：

第 0 代： 初始 points = [[0, 0, 0], [6, 6, 6]]。

target = [3, 3, 3] 不存在于第 0 代中。

第 1 代： 对于第 0 代中的每一对点，我们创建新的点。

使用 [0, 0, 0] 和 [6, 6, 6]，我们生成 [3, 3, 3]。

第 1 代之后，points = [[0, 0, 0], [6, 6, 6], [3, 3, 3]]。

target = [3, 3, 3] 在第 1 代中被找到，因此最小的 k 为 1。

题目来自力扣3923。

整体过程描述 1. 初始化第 0 代

• 将输入的points数组中的所有点存入一个集合（或映射）中，作为第 0 代。

• 集合的作用是去重，因为题目保证初始点没有重复，但后续生成过程中可能会产生重复点，集合可以自动去除重复。

• 目标点也转换为同样的表示形式，方便后续比较。

2. 逐代生成新点

从第 0 代开始，进行循环，每一轮代表一代：

2.1 检查目标点

• 首先检查当前代的点集合中是否已经包含目标点。

• 如果包含，直接返回当前代数（第 0 代返回 0，第 1 代返回 1，以此类推）。

2.2 生成下一代

• 如果目标点不在当前代中，则开始生成下一代。

• 复制当前代的点集合，作为下一代的基础（下一代包含上一代的所有点，因为旧点会保留）。

• 遍历当前代中的所有点对（允许同一个点与自身配对，但代码中实际是双重循环遍历集合中的所有点，包括相同点；不过题目要求两个不同点，这里代码实现上可能稍宽松，但根据题意，如果两点坐标相同，生成的还是同一个点，不会有新贡献）。

• 对于每一对点p和q：

• 计算新点的三个坐标：

• 新 x = (p.x + q.x) 整除 2

• 新 y = (p.y + q.y) 整除 2

• 新 z = (p.z + q.z) 整除 2

• 这里整除是向下取整，对于非负整数来说就是普通整数除法。

• 将新点加入下一代集合中。

• 由于集合自动去重，最终下一代集合包含了所有上一代点以及所有新生成的点。

2.3 判断是否继续

• 比较下一代集合的大小与当前代集合的大小。

• 如果两者大小相同，说明这一代没有产生任何新的点（所有可能的平均值点都已经在上一代中存在），那么再往后也不会有新点出现，目标点不可能再出现，返回 -1。

• 如果下一代集合更大，说明有新的点产生，将当前代更新为下一代，代数加 1，继续循环。

3. 终止条件

• 循环只有在两种情况下结束：

• 找到目标点，返回对应代数。

• 无法产生新点且目标点未找到，返回 -1。

复杂度分析 时间复杂度

• 设初始点数量为n（题目限制n <= 20）。

• 每一代中，点对枚举需要O(m^2)的时间，其中m是当前代点集合的大小。

• 由于坐标范围被限制在0到6之间（题目给定的范围），整个三维空间中的可能点数量是有限的，最多为7 * 7 * 7 = 343个点。

• 因此，随着代数增加，点集合大小m最多增长到 343 后就不再增长（或很快饱和）。

• 在最坏情况下，每一代都需要遍历所有m个点的所有点对，复杂度为O(m^2)。

• 因为m上界是 343，所以单代复杂度上界是O(343^2) = O(117649)，这是一个常数级的上界。

• 代数数量也不会无限增加，因为点集合大小有限，最多经过343 - n次增长后就会停止（每次增长至少增加 1 个点）。

• 所以总的时间复杂度在最坏情况下是O(343^2 * 343)级别，但实际远小于这个值，因为通常不会每一代都达到最大点集。从渐进角度看，由于坐标范围固定，可以认为是常数时间；如果推广到一般情况（坐标范围很大），则时间复杂度会与坐标空间大小有关，但本题中坐标范围固定，所以整体是O(1)常数级。

更准确地，若以V表示所有可能点的数量（本题中V = 343），则时间复杂度为O(V^3)以内，但实际操作中远低于此。

额外空间复杂度

• 主要使用两个集合（当前代和下一代），每个集合最多存储V个点（V = 343）。

• 每个点存储三个整数，空间占用常数。

• 因此额外空间复杂度为O(V)，即O(343)，也是常数级。

• 如果推广到坐标范围较大的情况，额外空间为O(V)，其中V是三维坐标空间中所有可能点的数量。

总结

算法核心是模拟“逐代生成”的过程，利用集合去重和有限坐标空间的特性，保证循环能终止。由于坐标范围很小（0~6），整体时间和空间复杂度都是常数级，实际运行效率很高。

Go完整代码如下：

package main

 import (
    "fmt"
    "maps"
)

 func minGenerations(points [][]int, target []int) int {
    type point struct{ x, y, z int }
    tar := point{target[0], target[1], target[2]}

     cur := make(map[point]struct{}, len(points))
    for _, p := range points {
        cur[point{p[0], p[1], p[2]}] = struct{}{}
    }

     for ans := 0; ; ans++ {
        if _, ok := cur[tar]; ok {
            return ans
        }

         nxt := maps.Clone(cur)
        for p := range cur {
            for q := range cur { // 枚举 cur 中的所有点对 (p, q)
                nxt[point{(p.x + q.x) / 2, (p.y + q.y) / 2, (p.z + q.z) / 2}] = struct{}{}
            }
        }

         if len(nxt) == len(cur) { // 没有产生新的点
            return -1
        }

         cur = nxt
    }
}

 func main() {
    points := [][]int{{0, 0, 0}, {6, 6, 6}}
    target := []int{3, 3, 3}
    result := minGenerations(points, target)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def min_generations(points, target):
    tar = tuple(target)
    cur = set()
    for p in points:
        cur.add(tuple(p))
    ans = 0
    while True:
        if tar in cur:
            return ans
        nxt = set(cur)
        cur_list = list(cur)
        # 枚举所有点对 (p, q)
        for i in range(len(cur_list)):
            for j in range(len(cur_list)):
                p = cur_list[i]
                q = cur_list[j]
                new_point = (
                    (p[0] + q[0]) // 2,
                    (p[1] + q[1]) // 2,
                    (p[2] + q[2]) // 2
                )
                nxt.add(new_point)
        if len(nxt) == len(cur):  # 没有产生新的点
            return -1
        cur = nxt
        ans += 1

 # 测试
if __name__ == "__main__":
    points = [[0, 0, 0], [6, 6, 6]]
    target = [3, 3, 3]
    result = min_generations(points, target)
    print(result)

C++完整代码如下：

  

  

  

  


 using namespace std;

 int minGenerations(vector 
 
 int 
 >>& points, vector< 
 int 
 >& target) { 
 
 
      
 // 使用 tuple 表示三维点 
 
 
     using Point = tuple< 
 int 
 ,  
 int 
 ,  
 int 
 >; 
 
 
 
 
     Point tar = make_tuple(target[ 
 0 
 ], target[ 
 1 
 ], target[ 
 2 
 ]); 
 
 
 
 
     set 
 
 cur; 
 
 
 
      
 for 
  (auto& p : points) { 
 
 
         cur.insert(make_tuple(p[ 
 0 
 ], p[ 
 1 
 ], p[ 
 2 
 ])); 
 
 
     } 
 
 
 
 
      
 for 
  ( 
 int 
  ans =  
 0 
 ; ; ans++) { 
 
 
          
 if 
  (cur.find(tar) != cur.end()) { 
 
 
              
 return 
  ans; 
 
 
         } 
 
 
 
 
         set 
 
 nxt = cur;   
 
 // 复制当前集合 
 
 
 
 
          
 // 枚举所有点对 (p, q) 
 
 
          
 for 
  (auto& p : cur) { 
 
 
              
 for 
  (auto& q : cur) { 
 
 
                 Point new_point = make_tuple( 
 
 
                     (get< 
 0 
 >(p) + get< 
 0 
 >(q)) /  
 2 
 , 
 
 
                     (get< 
 1 
 >(p) + get< 
 1 
 >(q)) /  
 2 
 , 
 
 
                     (get< 
 2 
 >(p) + get< 
 2 
 >(q)) /  
 2 
 
 
                     ); 
 
 
                 nxt.insert(new_point); 
 
 
             } 
 
 
         } 
 
 
 
 
          
 if 
  (nxt.size() == cur.size()) {   
 // 没有产生新的点 
 
 
              
 return 
   
 -1 
 ; 
 
 
         } 
 
 
 
 
         cur = nxt; 
 
 
     } 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector 
 
 int 
 >> points = {{ 
 0 
 ,  
 0 
 ,  
 0 
 }, { 
 6 
 ,  
 6 
 ,  
 6 
 }}; 
 
 
     vector< 
 int 
 > target = { 
 3 
 ,  
 3 
 ,  
 3 
 }; 
 
 
      
 int 
  result = minGenerations(points, target); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。