Medium

题目描述

给定一个 m x n 的网格 image，表示一个灰度图像，其中 image[i][j] 表示强度在 [0..255] 范围内的像素。还给定一个非负整数 threshold。

如果两个像素共享一条边，则它们是相邻的。

区域是一个 3 x 3 的子网格，其中任意两个相邻像素之间的强度绝对差值小于或等于 threshold。

区域中的所有像素都属于该区域，注意一个像素可以属于多个区域。

你需要计算一个 m x n 的网格 result，其中 result[i][j] 是 image[i][j] 所属区域的平均强度，向下舍入到最近的整数。如果 image[i][j] 属于多个区域，则 result[i][j] 是这些区域的向下舍入平均强度的平均值，向下舍入到最近的整数。如果 image[i][j] 不属于任何区域，则 result[i][j] 等于 image[i][j]。

返回网格 result。

示例 1：

输入：image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3
输出：[[9,9,9,9],[9,9,9,9],[9,9,9,9]]

示例 2：

输入：image = [[10,20,30],[15,25,35],[20,30,40],[25,35,45]], threshold = 12
输出：[[25,25,25],[27,27,27],[27,27,27],[30,30,30]]

示例 3：

输入：image = [[5,6,7],[8,9,10],[11,12,13]], threshold = 1
输出：[[5,6,7],[8,9,10],[11,12,13]]

提示：

  • 3 <= n, m <= 500
  • 0 <= image[i][j] <= 255
  • 0 <= threshold <= 255

解题思路

这道题需要找到所有有效的 3×3 区域，然后计算每个像素点在所有覆盖它的区域中的平均强度。

解题思路：

  1. 识别有效区域：遍历所有可能的 3×3 子网格，检查每个子网格是否构成有效区域。有效区域的条件是：任意两个相邻像素的强度差值不超过阈值。

  2. 区域验证：对于每个 3×3 子网格，需要检查所有相邻像素对的强度差值。相邻像素包括水平相邻和垂直相邻的像素。

  3. 累积计算：使用两个辅助数组 sum 和 count。对于每个有效区域，计算区域的平均强度（向下取整），然后将这个值加到区域内每个像素的 sum 中，并将对应的 count 加1。

  4. 结果计算：对于每个像素位置 (i,j)：

    • 如果 count[i][j] > 0，说明该像素属于至少一个区域，结果为 sum[i][j] / count[i][j]（向下取整）
    • 如果 count[i][j] == 0，说明该像素不属于任何区域，结果为原始像素值 image[i][j]

这种方法的时间复杂度是 O(m×n)，空间复杂度也是 O(m×n)，其中需要遍历所有可能的 3×3 子网格并进行验证。

代码实现

class Solution {
public:
    vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
        int m = image.size(), n = image[0].size();
        vector<vector<int>> sum(m, vector<int>(n, 0));
        vector<vector<int>> count(m, vector<int>(n, 0));
        
        // 检查所有可能的3x3子网格
        for (int i = 0; i <= m - 3; i++) {
            for (int j = 0; j <= n - 3; j++) {
                // 验证当前3x3子网格是否为有效区域
                bool valid = true;
                for (int x = i; x < i + 3 && valid; x++) {
                    for (int y = j; y < j + 3 && valid; y++) {
                        // 检查右边相邻像素
                        if (y < j + 2 && abs(image[x][y] - image[x][y + 1]) > threshold) {
                            valid = false;
                        }
                        // 检查下边相邻像素
                        if (x < i + 2 && abs(image[x][y] - image[x + 1][y]) > threshold) {
                            valid = false;
                        }
                    }
                }
                
                if (valid) {
                    // 计算区域平均强度
                    int regionSum = 0;
                    for (int x = i; x < i + 3; x++) {
                        for (int y = j; y < j + 3; y++) {
                            regionSum += image[x][y];
                        }
                    }
                    int regionAvg = regionSum / 9;
                    
                    // 更新区域内每个像素的sum和count
                    for (int x = i; x < i + 3; x++) {
                        for (int y = j; y < j + 3; y++) {
                            sum[x][y] += regionAvg;
                            count[x][y]++;
                        }
                    }
                }
            }
        }
        
        // 计算结果
        vector<vector<int>> result(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (count[i][j] > 0) {
                    result[i][j] = sum[i][j] / count[i][j];
                } else {
                    result[i][j] = image[i][j];
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        m, n = len(image), len(image[0])
        sum_grid = [[0] * n for _ in range(m)]
        count_grid = [[0] * n for _ in range(m)]
        
        # 检查所有可能的3x3子网格
        for i in range(m - 2):
            for j in range(n - 2):
                # 验证当前3x3子网格是否为有效区域
                valid = True
                for x in range(i, i + 3):
                    for y in range(j, j + 3):
                        # 检查右边相邻像素
                        if y < j + 2 and abs(image[x][y] - image[x][y + 1]) > threshold:
                            valid = False
                            break
                        # 检查下边相邻像素
                        if x < i + 2 and abs(image[x][y] - image[x + 1][y]) > threshold:
                            valid = False
                            break
                    if not valid:
                        break
                
                if valid:
                    # 计算区域平均强度
                    region_sum = 0
                    for x in range(i, i + 3):
                        for y in range(j, j + 3):
                            region_sum += image[x][y]
                    region_avg = region_sum // 9
                    
                    # 更新区域内每个像素的sum和count
                    for x in range(i, i + 3):
                        for y in range(j, j + 3):
                            sum_grid[x][y] += region_avg
                            count_grid[x][y] += 1
        
        # 计算结果
        result = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if count_grid[i][j] > 0:
                    result[i][j] = sum_grid[i][j] // count_grid[i][j]
                else:
                    result[i][j] = image[i][j]
        
        return result

public class Solution {
    public int[][] ResultGrid(int[][] image, int threshold) {
        int m = image.Length, n = image[0].Length;
        int[][] sum = new int[m][];
        int[][] count = new int[m][];
        
        for (int i = 0; i < m; i++) {
            sum[i] = new int[n];
            count[i] = new int[n];
        }
        
        // 检查所有可能的3x3子网格
        for (int i = 0; i <= m - 3; i++) {
            for (int j = 0; j <= n - 3; j++) {
                // 验证当前3x3子网格是否为有效区域
                bool valid = true;
                for (int x = i; x < i + 3 && valid; x++) {
                    for (int y = j; y < j + 3 && valid; y++) {
                        // 检查右边相邻像素
                        if (y < j + 2 && Math.Abs(image[x][y] - image[x][y + 1]) > threshold) {
                            valid = false;
                        }
                        // 检查下边相邻像素
                        if (x < i + 2 && Math.Abs(image[x][y] - image[x + 1][y]) > threshold) {
                            valid = false;
                        }
                    }
                }
                
                if (valid) {
                    // 计算区域平均强度
                    int regionSum = 0;
                    for (int x = i; x < i + 3; x++) {
                        for (int y = j; y < j + 3; y++) {
                            regionSum += image[x][y];
                        }
                    }
                    int regionAvg = regionSum / 9;
                    
                    // 更新区域内每个像素的sum和count
                    for (int x = i; x < i + 3; x++) {
                        for (int y = j; y < j + 3; y++) {
                            sum[x][y] += regionAvg;
                            count[x][y]++;
                        }
                    }
                }
            }
        }
        
        // 计算结果
        int[][] result = new int[m][];
        for (int i = 0; i < m; i++) {
            result[i] = new int[n];
            for (int j = 0; j < n; j++) {
                if (count[i][j] > 0) {
                    result[i][j] = sum[i][j] / count[i][j];
                } else {
                    result[i][j] = image[i][j];
                }
            }
        }
        
        return result;
    }
}

var resultGrid = function(image, threshold) {
    const m = image.length, n = image[0].length;
    const sum = Array(m).fill().map(() => Array(n).fill(0));
    const count = Array(m).fill().map(() => Array(n).fill(0));
    
    // 检查所有可能的3x3子网格
    for (let i = 0; i <= m - 3; i++) {
        for (let j = 0; j <= n - 3; j++) {
            // 验证当前3x3子网格是否为有效区域
            let valid = true;
            outer: for (let x = i; x < i + 3; x++) {
                for (let y = j; y < j + 3; y++) {
                    // 检查右边相邻像素
                    if (y < j + 2 && Math.abs(image[x][y] - image[x][y + 1]) > threshold) {
                        valid = false;
                        break outer;
                    }
                    // 检查下边相邻像素
                    if (x < i + 2 && Math.abs(image[x][y] - image[x + 1][y]) > threshold) {
                        valid = false;
                        break outer;
                    }
                }
            }
            
            if (valid) {
                // 计算区域平均强度
                let regionSum = 0;
                for (let x = i; x < i + 3; x++) {
                    for (let y = j; y < j + 3; y++) {
                        regionSum += image[x][y];
                    }
                }
                const regionAvg = Math.floor(regionSum / 9);
                
                // 更新区域内每个像素的sum和count
                for (let x = i; x < i + 3; x++) {
                    for (let y = j; y < j + 3; y++) {
                        sum[x][y] += regionAvg;
                        count[x][y]++;
                    }
                }
            }
        }
    }
    
    // 计算结果
    const result = Array(m).fill().map(() => Array(n));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (count[i][j] > 0) {
                result[i][j] = Math.floor(sum[i][j] / count[i][j]);
            } else {
                result[i][j] = image[i][j];
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m × n)
空间复杂度O(m × n)

其中 m 和 n 分别是图像的行数和列数。虽然需要检查每个 3×3 子网格，但总的操作次数仍然是 O(m × n) 级别的。空间复杂度主要来自于存储累积和与计数的辅助数组。

相关题目