LeetCode - 매트릭스 제로

12023 단어 LeetCode
m x n 의 행렬 을 지정 합 니 다. 하나의 요소 가 0 이면 줄 과 열 에 있 는 모든 요 소 를 0 으로 설정 합 니 다.제자리 알고리즘 을 사용 하 세 요.
예시 1:
  : 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
  : 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

예시 2:
  : 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
  : 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

진급:
  • 직접적인 해결 방안 은 O (mn) 의 추가 공간 을 사용 하 는 것 이지 만 이것 은 좋 은 해결 방안 이 아니다.
  • 간단 한 개선 방안 은 O (m + n) 의 추가 공간 을 사용 하 는 것 이지 만 이것 은 가장 좋 은 해결 방안 이 아니다.
  • 상수 공간의 해결 방안 을 생각해 낼 수 있 습 니까?

  • 우선 폭력, 폭력 이 통 하지 않 는 다 고 생각 하고 생각 을 바 꾸 었 더 니 녹색 이 되 었 다 >...
    public class demo {
        public static void setZeroes(int[][] matrix) {
            List<List<Integer>> zero = new ArrayList<>();
            for(int i=0;i<matrix.length;i++){
                for(int j=0;j<matrix[i].length;j++){
                    if(matrix[i][j] == 0){
                        List<Integer> temp = new ArrayList<>();
                        temp.add(i);
                        temp.add(j);
                        zero.add(temp);
                    }
                }
            }
    
            for(List<Integer> temp:zero){
               int r = temp.get(0);
               int c = temp.get(1);
               //  0
                for(int i=0;i<matrix[r].length;i++){
                    matrix[r][i] = 0;
                }
                //  0
                for(int j=0;j<matrix.length;j++){
                    matrix[j][c] = 0;
                }
            }
        }   
    }
    

    좋은 웹페이지 즐겨찾기