Medium

题目描述

给你一个大小为 m x n 的二维整数数组 grid。

你必须从网格的每一行中恰好选择一个整数。

返回一个整数，表示从每行选择的整数的最小可能按位或值。

示例 1：

输入：grid = [[1,5],[2,4]]
输出：3
解释：
从第一行选择 1，从第二行选择 2。
1 | 2 = 3 的按位或值是最小可能的。

示例 2：

输入：grid = [[3,5],[6,4]]
输出：5
解释：
从第一行选择 5，从第二行选择 4。
5 | 4 = 5 的按位或值是最小可能的。

示例 3：

输入：grid = [[7,9,8]]
输出：7
解释：
选择 7 可以得到最小的按位或值。

约束条件：

  • 1 <= m == grid.length <= 10^5
  • 1 <= n == grid[i].length <= 10^5
  • m * n <= 10^5
  • 1 <= grid[i][j] <= 10^5

解题思路

这道题要求我们从每行选择一个数，使得所有选择数字的按位或值最小。

核心思路：贪心 + 位运算

按位或运算有一个重要性质：一旦某个位被设置为1，就无法通过后续的或运算变回0。因此，我们应该尽可能避免设置高位的位。

算法步骤：

  1. 从最高位开始检查每一位（通常检查到第17位就足够，因为数字最大为10^5）
  2. 对于当前位，检查是否可以在每一行都找到至少一个数字，使得该位为0
  3. 如果可以，则该位在最终结果中保持为0；否则该位必须为1
  4. 使用动态规划或贪心策略：维护当前可能的最小或值集合

优化思路： 我们可以用集合来维护每一步可能的所有或值。对于每一行，我们将当前集合中的每个值与该行的每个数字进行或运算，得到新的可能值集合。为了避免集合过大，我们只保留较小的值。

由于按位或的单调性，如果我们已经有了值A，而A的所有位都包含在B中（即A | B = B），那么B就可以被A替代，因为A更小且能产生相同或更好的结果。

代码实现

class Solution {
public:
    int minimumOR(vector<vector<int>>& grid) {
        set<int> current = {0};
        
        for (auto& row : grid) {
            set<int> next;
            for (int val : current) {
                for (int num : row) {
                    next.insert(val | num);
                }
            }
            current = move(next);
            
            // 优化：只保留较小的值，因为按位或是单调递增的
            if (current.size() > 50) {
                set<int> pruned;
                int count = 0;
                for (int val : current) {
                    pruned.insert(val);
                    if (++count >= 50) break;
                }
                current = move(pruned);
            }
        }
        
        return *current.begin();
    }
};

class Solution:
    def minimumOR(self, grid: List[List[int]]) -> int:
        current = {0}
        
        for row in grid:
            next_set = set()
            for val in current:
                for num in row:
                    next_set.add(val | num)
            current = next_set
            
            # 优化：只保留较小的值
            if len(current) > 50:
                current = set(sorted(current)[:50])
        
        return min(current)

public class Solution {
    public int MinimumOR(int[][] grid) {
        HashSet<int> current = new HashSet<int> { 0 };
        
        foreach (var row in grid) {
            HashSet<int> next = new HashSet<int>();
            foreach (int val in current) {
                foreach (int num in row) {
                    next.Add(val | num);
                }
            }
            current = next;
            
            // 优化：只保留较小的值
            if (current.Count > 50) {
                var sortedValues = current.OrderBy(x => x).Take(50);
                current = new HashSet<int>(sortedValues);
            }
        }
        
        return current.Min();
    }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumOR = function(grid) {
    let current = new Set([0]);
    
    for (let row of grid) {
        let next = new Set();
        for (let val of current) {
            for (let num of row) {
                next.add(val | num);
            }
        }
        current = next;
        
        // 优化：只保留较小的值
        if (current.size > 50) {
            let sortedValues = Array.from(current).sort((a, b) => a - b).slice(0, 50);
            current = new Set(sortedValues);
        }
    }
    
    return Math.min(...current);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m × n × k)，其中 k 是每步保留的状态数量，通常为常数
空间复杂度O(k)，用于存储可能的或值集合