矩阵
更新: 9/3/2025 字数: 0 字 时长: 0 分钟
矩阵置零
java
/**
* <p>此方法解决“矩阵置零”问题，要求使用原地算法 (O(1) 额外空间) 和 O(M*N) 时间复杂度。</p>
* <p>核心思想：利用矩阵的第一行和第一列来充当“标记数组”，记录哪些行和列需要被置为零。
* 为了处理第一行和第一列本身可能需要被置零的情况，使用两个额外的布尔变量来记录它们的状态。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化标记变量和获取维度：</strong>
* <ul>
* <li>{@code boolean rowZero = false;}: 记录第一行是否需要被置零。</li>
* <li>{@code boolean colZero = false;}: 记录第一列是否需要被置零。</li>
* <li>获取矩阵的行数 {@code m = matrix.length} 和列数 {@code n = matrix[0].length}。</li>
* </ul>
* </li>
* <li><strong>检查第一行和第一列是否包含 0：</strong>
* <ul>
* <li>遍历第一行（{@code matrix[0][j]}），如果发现任何一个元素为 0，则将 {@code rowZero} 设为 {@code true}。</li>
* <li>遍历第一列（{@code matrix[i][0]}），如果发现任何一个元素为 0，则将 {@code colZero} 设为 {@code true}。</li>
* </ul>
* </li>
* <li><strong>使用第一行和第一列作为标记 (处理内部区域)：</strong>
* <ul>
* <li>遍历矩阵的内部区域（从 {@code i = 1} 到 {@code m-1}，从 {@code j = 1} 到 {@code n-1}）。</li>
* <li>如果 {@code matrix[i][j] == 0}：
* <ul>
* <li>将 {@code matrix[i][0]} 置为 {@code 0} (标记第 {@code i} 行需要置零)。</li>
* <li>将 {@code matrix[0][j]} 置为 {@code 0} (标记第 {@code j} 列需要置零)。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>根据标记将内部区域置零：</strong>
* <ul>
* <li>再次遍历矩阵的内部区域（从 {@code i = 1} 到 {@code m-1}，从 {@code j = 1} 到 {@code n-1}）。</li>
* <li>如果 {@code matrix[i][0] == 0} (表示第 {@code i} 行需要置零) 或者 {@code matrix[0][j] == 0} (表示第 {@code j} 列需要置零)：
* <ul>
* <li>将 {@code matrix[i][j]} 置为 {@code 0}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>根据初始布尔变量处理第一行和第一列：</strong>
* <ul>
* <li>如果 {@code rowZero} 为 {@code true}，遍历第一行，将其所有元素置为 {@code 0}。</li>
* <li>如果 {@code colZero} 为 {@code true}，遍历第一列，将其所有元素置为 {@code 0}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(M*N)}。
* <ul>
* <li>有多次遍历矩阵的操作，每次遍历的复杂度都是 {@code O(M*N)}。
* 因此总时间复杂度为 {@code O(M*N)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了几个常数级别的额外变量（{@code rowZero}, {@code colZero}, {@code m}, {@code n}）。
* 对矩阵本身进行的修改不计入额外空间。</li>
* </ul>
* </li>
* </ul>
*/
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int m = matrix.length;
int n = matrix[0].length;
boolean rowZero = false; // 标记第一行是否需要被置零
boolean colZero = false; // 标记第一列是否需要被置零
// 1. 检查第一行是否包含 0
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
rowZero = true;
break; // 只要找到一个 0 即可
}
}
// 2. 检查第一列是否包含 0
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
colZero = true;
break; // 只要找到一个 0 即可
}
}
// 3. 使用第一行和第一列作为标记 (处理内部区域：从 [1][1] 开始)
// 如果 matrix[i][j] 为 0，则将其对应的第一行元素和第一列元素置 0
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0; // 标记第 i 行
matrix[0][j] = 0; // 标记第 j 列
}
}
}
// 4. 根据标记将内部区域置零 (从 [1][1] 开始)
// 注意：这里要先处理内部区域，否则如果先处理了第一行/列，
// 那么内部区域的标记可能会被覆盖，导致错误。
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 5. 根据 rowZero 和 colZero 标记，处理第一行和第一列
// 这一步必须在最后执行，以避免影响对内部区域的标记判断。
if (rowZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (colZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}螺旋矩阵
java
/**
* <p>此方法解决“螺旋矩阵”问题，按照顺时针螺旋顺序返回矩阵中的所有元素。</p>
* <p>核心思想是模拟螺旋遍历的过程，通过维护四个边界变量 (上、下、左、右) 来控制遍历的范围，
* 每次遍历完一个方向后收缩相应的边界，直到所有元素都被遍历。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个 {@link java.util.ArrayList} {@code result} 用于存储螺旋顺序的元素。</li>
* <li>获取矩阵的行数 {@code m = matrix.length} 和列数 {@code n = matrix[0].length}。
* 如果矩阵为空，直接返回空列表。</li>
* <li>初始化边界变量：
* <ul>
* <li>{@code int top = 0; } (当前层的上边界行索引)</li>
* <li>{@code int bottom = m - 1; } (当前层的下边界行索引)</li>
* <li>{@code int left = 0; } (当前层的左边界列索引)</li>
* <li>{@code int right = n - 1; } (当前层的右边界列索引)</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>主循环：</strong> 当 {@code top <= bottom} 并且 {@code left <= right} 时，循环继续。
* 这确保了还有未遍历的区域。
* <ul>
* <li><strong>从左到右遍历上边界：</strong>
* <ul>
* <li>遍历 {@code j} 从 {@code left} 到 {@code right}，将 {@code matrix[top][j]} 添加到 {@code result}。</li>
* <li>{@code top++} (上边界下移，缩小范围)。</li>
* </ul>
* </li>
* <li><strong>从上到下遍历右边界：</strong>
* <ul>
* <li>在执行前，检查是否还有剩余行可以遍历 (即 {@code top <= bottom})。</li>
* <li>遍历 {@code i} 从 {@code top} 到 {@code bottom}，将 {@code matrix[i][right]} 添加到 {@code result}。</li>
* <li>{@code right--} (右边界左移，缩小范围)。</li>
* </ul>
* </li>
* <li><strong>从右到左遍历下边界：</strong>
* <ul>
* <li>在执行前，检查是否还有剩余行和列可以遍历 (即 {@code top <= bottom && left <= right})。
* 这是为了处理单行或单列矩阵的情况，避免重复遍历。</li>
* <li>遍历 {@code j} 从 {@code right} 到 {@code left} (注意是递减)，将 {@code matrix[bottom][j]} 添加到 {@code result}。</li>
* <li>{@code bottom--} (下边界上移，缩小范围)。</li>
* </ul>
* </li>
* <li><strong>从下到上遍历左边界：</strong>
* <ul>
* <li>在执行前，检查是否还有剩余列可以遍历 (即 {@code top <= bottom && left <= right})。</li>
* <li>遍历 {@code i} 从 {@code bottom} 到 {@code top} (注意是递减)，将 {@code matrix[i][left]} 添加到 {@code result}。</li>
* <li>{@code left++} (左边界右移，缩小范围)。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回 {@code result} 列表。</strong></li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(M*N)}。
* <ul>
* <li>每个元素恰好被访问一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)} (不包括返回结果列表)。
* <ul>
* <li>我们只使用了常数个额外变量来控制边界和循环。</li>
* <li>如果将结果列表计算在内，则为 {@code O(M*N)}。</li>
* </ul>
* </li>
* </ul>
*/
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return result;
}
int m = matrix.length;
int n = matrix[0].length;
int top = 0; // 上边界行索引
int bottom = m - 1; // 下边界行索引
int left = 0; // 左边界列索引
int right = n - 1; // 右边界列索引
while (top <= bottom && left <= right) {
// 1. 从左到右遍历上边界
for (int j = left; j <= right; j++) {
result.add(matrix[top][j]);
}
top++; // 上边界下移
// 检查是否还有剩余行可以遍历
if (top > bottom) break;
// 2. 从上到下遍历右边界
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--; // 右边界左移
// 检查是否还有剩余列可以遍历
if (left > right) break;
// 3. 从右到左遍历下边界
// 只有当有多个行时才需要向左遍历，避免单行重复
for (int j = right; j >= left; j--) {
result.add(matrix[bottom][j]);
}
bottom--; // 下边界上移
// 检查是否还有剩余行可以遍历
if (top > bottom) break;
// 4. 从下到上遍历左边界
// 只有当有多个列时才需要向上遍历，避免单列重复
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++; // 左边界右移
// 检查是否还有剩余列可以遍历
if (left > right) break;
}
return result;
}旋转图像
java
/**
* <p>此方法解决“旋转图像”问题，要求将 n x n 的矩阵顺时针旋转 90 度，且必须在原地进行。</p>
* <p>核心思想是将旋转分解为两个简单的原地操作：
* 1. 水平翻转 (沿水平中线翻转)。
* 2. 主对角线翻转 (将 {@code matrix[i][j]} 与 {@code matrix[j][i]} 交换)。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>获取矩阵维度：</strong>
* <ul>
* <li>获取矩阵的边长 {@code n = matrix.length}。
* 如果矩阵为空或为单行/单列，直接返回。</li>
* </ul>
* </li>
* <li><strong>水平翻转 (Flip Horizontally)：</strong>
* <ul>
* <li>遍历上半部分的行 (从 {@code i = 0} 到 {@code n/2 - 1})。
* 例如，对于 3x3 矩阵，{@code i = 0}；对于 4x4 矩阵，{@code i = 0, 1}。</li>
* <li>对于每一行 {@code i}，遍历所有列 (从 {@code j = 0} 到 {@code n - 1})。</li>
* <li>交换 {@code matrix[i][j]} 和 {@code matrix[n - 1 - i][j]}。
* 这将使得第一行与最后一行交换，第二行与倒数第二行交换，依此类推。</li>
* </ul>
* </li>
* <li><strong>主对角线翻转 (Transpose)：</strong>
* <ul>
* <li>遍历矩阵的下三角或上三角区域 (从 {@code i = 0} 到 {@code n - 1}，从 {@code j = i + 1} 到 {@code n - 1})。
* 从 {@code j = i + 1} 开始是为了确保每个元素只被交换一次，避免重复操作或交换回原位。</li>
* <li>交换 {@code matrix[i][j]} 和 {@code matrix[j][i]}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>示例 (以 3x3 矩阵为例)：</h3>
* <p><strong>原始矩阵:</strong></p>
* <pre>
* 1 2 3
* 4 5 6
* 7 8 9
* </pre>
* <p><strong>1. 水平翻转后:</strong> (第 0 行与第 2 行交换)</p>
* <pre>
* 7 8 9
* 4 5 6
* 1 2 3
* </pre>
* <p><strong>2. 主对角线翻转后:</strong> (交换 {@code matrix[i][j]} 和 {@code matrix[j][i]} )</p>
* <pre>
* 7 4 1
* 8 5 2
* 9 6 3
* </pre>
* <p>这正是顺时针旋转 90 度后的结果。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N^2)}。
* <ul>
* <li>水平翻转需要遍历大约一半的行，每行 {@code N} 个元素，总计 {@code O(N*N/2)} = {@code O(N^2)}。</li>
* <li>主对角线翻转需要遍历大约一半的元素，总计 {@code O(N^2/2)} = {@code O(N^2)}。</li>
* <li>因此总时间复杂度为 {@code O(N^2)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>所有操作都在原矩阵上进行，只使用了常数个额外变量用于交换。</li>
* </ul>
* </li>
* </ul>
*/
public void rotate(int[][] matrix) {
int n = matrix.length;
if (n == 0 || n == 1) { // 空矩阵或 1x1 矩阵无需旋转
return;
}
// 1. 水平翻转 (上下翻转)
// 遍历上半部分的行
for (int i = 0; i < n / 2; i++) {
// 遍历所有列
for (int j = 0; j < n; j++) {
// 交换 matrix[i][j] 和 matrix[n-1-i][j]
int temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - i][j];
matrix[n - 1 - i][j] = temp;
}
}
// 2. 主对角线翻转 (转置)
// 遍历上半三角形区域
for (int i = 0; i < n; i++) {
// j 从 i+1 开始，确保只交换一次 (避免重复交换)
for (int j = i + 1; j < n; j++) {
// 交换 matrix[i][j] 和 matrix[j][i]
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}搜索二维矩阵 II
java
/**
* <p>此方法解决“搜索二维矩阵 II”问题，利用矩阵的特殊排序特性，实现高效搜索。</p>
* <p>矩阵特性：每行从左到右升序，每列从上到下升序。</p>
* <p>核心思想是：从矩阵的右上角（或左下角）开始搜索。
* 这个起始点具有独特的性质：向上/向左的值更小，向下/向右的值更大。
* 每次比较都能排除一行或一列，从而逐步缩小搜索范围。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化指针和维度：</strong>
* <ul>
* <li>获取矩阵的行数 {@code m = matrix.length} 和列数 {@code n = matrix[0].length}。</li>
* <li>如果矩阵为空 ({@code m == 0} 或 {@code n == 0})，则目标值不可能存在，直接返回 {@code false}。</li>
* <li>设置起始搜索位置：
* <ul>
* <li>{@code int row = 0; } (从第一行开始)</li>
* <li>{@code int col = n - 1; } (从最后一列开始，即右上角)</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>循环搜索：</strong>
* <ul>
* <li>当 {@code row < m} (行索引在有效范围内) 并且 {@code col >= 0} (列索引在有效范围内) 时，循环继续。</li>
* <li>在循环内部，进行比较：
* <ul>
* <li>如果 {@code matrix[row][col] == target}：找到了目标值，返回 {@code true}。</li>
* <li>如果 {@code matrix[row][col] < target}：当前值太小。
* 因为当前行从左到右升序，所以当前元素左边的值更小，不可能等于 {@code target}。
* 因为当前列从上到下升序，所以当前元素下面的值更大，更有可能等于 {@code target}。
* 因此，向下移动一行：{@code row++}。</li>
* <li>如果 {@code matrix[row][col] > target}：当前值太大。
* 因为当前列从上到下升序，所以当前元素下面的值更大，更不可能等于 {@code target}。
* 因为当前行从左到右升序，所以当前元素左边的值更小，更有可能等于 {@code target}。
* 因此，向左移动一列：{@code col--}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>未找到：</strong>
* <ul>
* <li>如果循环结束，说明 {@code row} 超出了范围或者 {@code col} 超出了范围，但仍未找到 {@code target}。</li>
* <li>返回 {@code false}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(M + N)}。
* <ul>
* <li>在最坏情况下，搜索路径从右上角走到左下角 (或者反之)。</li>
* <li>每次迭代都会使 {@code row} 增加或 {@code col} 减少，因此最多进行 {@code M + N} 次迭代。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外变量来存储指针和维度。</li>
* </ul>
* </li>
* </ul>
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length; // 行数
int n = matrix[0].length; // 列数
// 从矩阵的右上角开始搜索
int row = 0;
int col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] == target) {
return true; // 找到目标值
} else if (matrix[row][col] < target) {
// 当前值太小，因为当前列向下是递增的，所以向下找
row++;
} else { // matrix[row][col] > target
// 当前值太大，因为当前行向左是递减的，所以向左找
col--;
}
}
return false; // 循环结束仍未找到，说明目标值不存在
}贡献者
LI SIR