2026-06-28：按位或的最小值。用go语言，给你一个大小为 m × n 的二维整数表 grid。你需要从 每一行 里 各选出一个数（同一行只选一个，

2026-06-28：按位或的最小值。用go语言，给你一个大小为 m × n 的二维整数表 grid。你需要从 每一行 里 各选出一个数（同一行只选一个，不能多选或少选）。把这些被选出的数做按位或运算（bitwise OR）。

你的目标是：让最终得到的 按位或结果尽可能小。返回这个 最小可能的按位或值。

1 <= m == grid.length <= 100000。

1 <= n == grid[i].length <= 100000。

m * n <= 100000。

1 <= grid[i][j] <= 100000。

输入： grid = [[1,5],[2,4]]。

输出： 3。

解释：

从第一行选择 1，从第二行选择 2。

1 | 2 = 3，这是最小可能值。

题目来自力扣3858。

一、代码整体执行分步详细流程 步骤1：先计算所有行最小值的或值or，确定二进制遍历上限

1. 遍历每一行，取出该行最小数字；

2. 将所有行最小值做按位或，得到变量or；

3. 作用：任何合法选法的或结果，一定 ≤ 这个or。
原因：每行选最小值时，单个数字本身最小，它们的或自然是一个上界；最终答案的二进制有效位数，不会超过or的二进制位数，后续只需要遍历这个范围内的比特位，不用遍历全部32/64位，减少循环次数。
示例：
第一行最小1，第二行最小2，or = 1 | 2 = 3，二进制11，有效比特位长度为2，只需处理第1位、第0位（从0开始计数）。

步骤2：从最高二进制位往低位逐位贪心判断，构造最小答案ans

初始ans = 0，从最高位i = bits.Len(uint(or)) - 1向下循环到0，每一位执行相同逻辑：

2.1 构造校验掩码 mask

公式：mask = ans | (1<
拆解掩码含义：

1.ans：已经确定好的高位比特（已经固定不能修改）；

2.1<：第i位以下所有低位全部置1；
整体mask规则：

•高于i的位：完全复制当前ans的高位，这部分是已经敲定的、不能改动的比特；

•第i位及所有低位：全部为1。

掩码作用：筛选满足「高位和ans完全匹配、第i位可以为0」的候选数字。

2.2 逐行校验：是否每行都存在符合条件的数字

内层遍历每一行，对每行内所有数字x做校验判断x | mask == mask：

1. 等式逻辑拆解：
x | mask = mask等价于x & (~mask) = 0
代表x所有高于i的比特，全部和ans的高位保持一致；同时x的第i位一定是0（低位无限制）。

2. 单行判断分支：

• 若该行找到任意一个x满足条件：说明本行可以选出一个「高位匹配ans、第i位为0」的数字，本行校验通过，直接跳过本行剩余数字，进入下一行校验；

• 若本行全部数字都不满足条件：本行不存在能让第i位为0的数字，说明最终答案的第i位必须置1。

2.3 根据校验结果更新ans

1. 若所有行都能找到符合条件的数字：当前第i位可以保持0，ans不做任何修改，直接处理下一个更低的比特位；

2. 若存在任意一行找不到符合条件的数字：第i位无法为0，执行ans |= 1 << i，把ans的第i位强制设为1，再处理下一个低位比特。

示例逐位推演 grid=[[1,5],[2,4]]

初始：ans=0，or=3，二进制长度2，i从1开始（高位），再i=0。

第1位（i=1，2^1=2）

mask = ans | (1<<1 -1) = 0 | 1 = 0b01
逐行校验：

• 第一行数字1(0b01)、5(0b101)
x=1：1 | 0b01 = 0b01 = mask，满足，本行通过；

• 第二行数字2(0b10)、4(0b100)
x=2：2 | 0b01 = 0b11 ≠ mask；x=4同理不满足。本行无符合条件数字。
结论：第1位必须为1，ans = 0 | (1<<1) = 2（0b10）。

第0位（i=0，2^0=1）

mask = ans | (1<<0 -1) = 2 | 0 = 0b10
逐行校验：

• 第一行数字1(0b01)：1 | 0b10 = 0b11≠0b10；5(0b101)：5 | 0b10=0b111≠0b10，无匹配？修正校验逻辑：
判断目标：数字高位和ans(0b10)一致，第0位为0。
数字高位是高于0的位（即第1位），必须等于ans第1位=1，同时第0位=0。
第一行：1二进制01（第1位是0，不匹配ans高位）、5是101（第1位0，不匹配）；
第二行：2是10（第1位1，第0位0，满足x|mask=10=mask）。
此时第一行没有满足条件的数字，说明第0位必须置1，ans = 2 | 1 = 3，循环结束。

最终ans=3，和题目输出一致。

步骤3：遍历完成所有比特位，返回ans

从高到低所有比特全部判断完毕，ans就是每行选一个数得到的最小或结果。

二、时间复杂度分析 变量定义

设总元素数量T = m * n，题目约束 T ≤ 1e5；
设数字最大二进制位数B：grid[i][j] ≤ 1e5，1e5二进制约17位，B≈17（常数）。

1. 第一步求每行最小值并计算初始or：遍历全部T个元素，复杂度 O(T)；

2. 外层比特循环：B次循环，B是固定常数；

3. 每层比特循环内部：遍历全部T个数字做校验，单次内层O(T)；
总时间复杂度：
O(T + B * T) = O(B*T)
B为常数，等价于O(T)，即 O(m*n)。

三、额外空间复杂度分析

代码仅使用固定数量临时变量：or、ans、i、mask、循环临时行row、数字x，无额外数组、切片、哈希表等动态存储；
不随输入规模m、n、T增长开辟存储空间。
额外空间复杂度：O(1)（常数空间）。

Go完整代码如下：

package main

 import (
    "fmt"
    "math/bits"
    "slices"
)

 func minimumOR(grid [][]int) (ans int) {
    or := 0
    for _, row := range grid {
        // 每行选个最小值，计算 OR
        or |= slices.Min(row)
    }
    // 答案 <= or，那么答案的二进制长度也 <= or 的二进制长度

     // 试填法：ans 的第 i 位能不能是 0？
    // 如果在每一行的能选的数字中，都存在第 i 位是 0 的数，那么 ans 的第 i 位可以是 0，否则必须是 1
    for i := bits.Len(uint(or)) - 1; i >= 0; i-- {
        mask := ans | (1<1) // mask 低于 i 的比特位全是 1，表示 grid[i][j] 的低位是 0 还是 1 无所谓
    next:
        for _, row := range grid {
            for _, x := range row {
                // x 的高于 i 的比特位，如果 mask 是 0，那么 x 的这一位必须也是 0（注意 mask 继承了 ans 高位中的 0）
                // x 的低于 i 的比特位，随意
                // x 的第 i 个比特位，我们期望它是 0
                if x|mask == mask { // x 可以选，且第 i 位是 0
                    continue next
                }
            }
            // 这一行的可选数字中，第 i 位全是 1
            ans |= 1 << i // ans 第 i 位必须是 1
            break         // 填下一位
        }
    }
    return
}

 func main() {
    grid := [][]int{{1, 5}, {2, 4}}
    result := minimumOR(grid)
    fmt.Println(result)
}

Python完整代码如下：

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

 from typing import List

 def minimumOR(grid: List[List[int]]) -> int:
    # 计算每行最小值的 OR，作为答案的上界
    or_val = 0
    for row in grid:
        or_val |= min(row)

     ans = 0
    # 从最高位向最低位尝试填 0
    for i in range(or_val.bit_length() - 1, -1, -1):
        # mask: 高于 i 的位与 ans 一致，低于 i 的位全为 1（可任意），第 i 位为 0
        mask = ans | ((1 << i) - 1)
        for row in grid:
            for x in row:
                # 如果 x 满足：高位与 ans 已固定的 0 对齐，且第 i 位为 0
                if (x | mask) == mask:
                    break
            else:
                # 这一行找不到满足条件的数，第 i 位必须填 1
                ans |= (1 << i)
                break
    return ans

 if __name__ == "__main__":
    grid = [[1, 5], [2, 4]]
    result = minimumOR(grid)
    print(result)

C++完整代码如下：

  

  

  



 int minimumOR(const std::vector 
 
 int 
 >>& grid) { 
 
 
      
 // 计算每行最小值的按位或，作为答案的上界 
 
 
      
 int 
  orVal =  
 0 
 ; 
 
 
      
 for 
  ( 
 const 
  auto& row : grid) { 
 
 
         orVal |= *std::min_element(row.begin(), row.end()); 
 
 
     } 
 
 
 
 
      
 // 计算 orVal 的二进制长度（位数） 
 
 
      
 int 
  bits =  
 0 
 ; 
 
 
      
 int 
  tmp = orVal; 
 
 
     while (tmp) { 
 
 
         ++bits; 
 
 
         tmp >>=  
 1 
 ; 
 
 
     } 
 
 
 
 
      
 int 
  ans =  
 0 
 ; 
 
 
      
 // 试填法：从高位到低位尝试让 ans 的第 i 位为 0 
 
 
      
 for 
  ( 
 int 
  i = bits -  
 1 
 ; i >=  
 0 
 ; --i) { 
 
 
          
 // mask: 低于 i 的位全为 1，第 i 位为 0，高于 i 的位与 ans 保持一致 
 
 
          
 int 
  mask = ans | (( 
 1 
  << i) -  
 1 
 ); 
 
 
 
 
          
 bool 
  possible =  
 true 
 ; 
 
 
          
 for 
  ( 
 const 
  auto& row : grid) { 
 
 
              
 bool 
  rowOk =  
 false 
 ; 
 
 
              
 for 
  ( 
 int 
  x : row) { 
 
 
                  
 // 检查 x 是否满足：高位对齐 ans 的 0 位，且第 i 位为 0 
 
 
                  
 if 
  ((x | mask) == mask) { 
 
 
                     rowOk =  
 true 
 ; 
 
 
                      
 break 
 ; 
 
 
                 } 
 
 
             } 
 
 
              
 if 
  (!rowOk) { 
 
 
                 possible =  
 false 
 ; 
 
 
                  
 break 
 ; 
 
 
             } 
 
 
         } 
 
 
 
 
          
 // 如果某一行无法选出第 i 位为 0 的数，则 ans 的第 i 位必须为 1 
 
 
          
 if 
  (!possible) { 
 
 
             ans |= ( 
 1 
  << i); 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     std::vector 
 
 int 
 >> grid = {{ 
 1 
 ,  
 5 
 }, { 
 2 
 ,  
 4 
 }}; 
 
 
      
 int 
  result = minimumOR(grid); 
 
 
     std::cout << result << std::endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 

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