原文:
Write an algorithm such that if an element in an MxN matrix is 0,its entire row and column is set to 0.
译文:
写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0.
解答:这道题有一个陷阱,如果在遍历矩阵的过程中遇到0就处理,就会出现问题。所以处理手段是:先记录0出现的位置,然后集中处理0所在行所在列着非常重要。
package com.zhuyu_deng.test; public class Test { public static void main(String args[]) { final int N = 10; int cnt = 1; int arr[][] = new int[N][N]; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { arr[i][j] = cnt++; } } arr[5][6] = 0; handleMatrix(arr); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { System.out.print(arr[i][j] + " "); } System.out.println(); } } private static void handleMatrix(int[][] arr) { boolean row[] = new boolean[arr.length]; boolean col[] = new boolean[arr.length]; for (int i = 0; i < arr.length; ++i) { for (int j = 0; j < arr[i].length; ++j) { if (arr[i][j] == 0) { row[i] = true; col[j] = true; } } } for (int i = 0; i < arr.length; ++i) { for (int j = 0; j < arr.length; ++j) if (row[i] || col[j]) arr[i][j] = 0; } } }