Medium

题目描述

给你一个 m x n 的整数矩阵 mat 和一个整数 target。

从矩阵的每一行中选择一个整数，使目标值 target 和所选元素和的绝对差值最小化。

返回最小的绝对差值。

两个数 a 和 b 之间的绝对差值是 a - b 的绝对值。

示例 1：

输入: mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
输出: 0
解释: 一种可能的选择是：
- 从第一行选择 1
- 从第二行选择 5
- 从第三行选择 7
所选元素和为 13，等于目标值，所以绝对差值是 0。

示例 2：

输入: mat = [[1],[2],[3]], target = 100
输出: 94
解释: 最好的选择是：
- 从第一行选择 1
- 从第二行选择 2
- 从第三行选择 3
所选元素和为 6，绝对差值是 94。

示例 3：

输入: mat = [[1,2,9,8,7]], target = 6
输出: 1
解释: 最好的选择是从第一行选择 7。绝对差值是 1。

约束条件：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 70
  • 1 <= mat[i][j] <= 70
  • 1 <= target <= 800

解题思路

这是一个典型的动态规划问题。我们需要从每一行选择一个元素，使得和与目标值的差值最小。

思路分析：

  1. 状态表示：使用集合记录当前可能达到的所有和值。初始时只有一个空和（0）。

  2. 状态转移：对于每一行，将当前集合中的每个和值加上该行的每个元素，得到新的可能和值集合。

  3. 优化策略：为了避免状态爆炸，我们可以进行剪枝：

    • 如果当前和已经远大于目标值，可以不继续扩展
    • 由于所有元素都是正数，和值只会增大，所以可以设定一个上界进行剪枝

  4. 最终答案：遍历所有可能的和值，找到与目标值差值最小的那个。

算法步骤：

  • 初始化可能和值集合为 {0}
  • 遍历每一行，对于当前集合中的每个和值，加上该行的每个元素
  • 使用剪枝优化：当和值过大时停止扩展
  • 最后计算所有可能和值与目标值的最小差值

这种方法的时间复杂度主要取决于可能和值的数量，通过合理剪枝可以大大降低实际运行时间。

代码实现

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        set<int> possible = {0};
        
        for (auto& row : mat) {
            set<int> next;
            for (int sum : possible) {
                for (int num : row) {
                    int newSum = sum + num;
                    // 剪枝：如果和值过大，跳过
                    if (newSum <= target + 4900) {  // 4900 = 70*70，最大可能的多余值
                        next.insert(newSum);
                    }
                }
            }
            possible = next;
        }
        
        int minDiff = INT_MAX;
        for (int sum : possible) {
            minDiff = min(minDiff, abs(sum - target));
        }
        
        return minDiff;
    }
};

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        possible = {0}
        
        for row in mat:
            next_possible = set()
            for curr_sum in possible:
                for num in row:
                    new_sum = curr_sum + num
                    # 剪枝：如果和值过大，跳过
                    if new_sum <= target + 4900:  # 4900 = 70*70
                        next_possible.add(new_sum)
            possible = next_possible
        
        return min(abs(s - target) for s in possible)

public class Solution {
    public int MinimizeTheDifference(int[][] mat, int target) {
        HashSet<int> possible = new HashSet<int> { 0 };
        
        foreach (int[] row in mat) {
            HashSet<int> next = new HashSet<int>();
            foreach (int sum in possible) {
                foreach (int num in row) {
                    int newSum = sum + num;
                    // 剪枝：如果和值过大，跳过
                    if (newSum <= target + 4900) {  // 4900 = 70*70
                        next.Add(newSum);
                    }
                }
            }
            possible = next;
        }
        
        int minDiff = int.MaxValue;
        foreach (int sum in possible) {
            minDiff = Math.Min(minDiff, Math.Abs(sum - target));
        }
        
        return minDiff;
    }
}

var minimizeTheDifference = function(mat, target) {
    let possible = new Set([0]);
    
    for (let row of mat) {
        let next = new Set();
        for (let sum of possible) {
            for (let num of row) {
                let newSum = sum + num;
                // 剪枝：如果和值过大，跳过
                if (newSum <= target + 4900) {  // 4900 = 70*70
                    next.add(newSum);
                }
            }
        }
        possible = next;
    }
    
    let minDiff = Infinity;
    for (let sum of possible) {
        minDiff = Math.min(minDiff, Math.abs(sum - target));
    }
    
    return minDiff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m × n × S)其中 m 是行数，n 是列数，S 是可能和值的数量。通过剪枝，S 通常远小于理论最大值
空间复杂度O(S)存储所有可能的和值，S 是可能和值的数量

相关题目