-
48일 (2643. Row With Maximum Ones) matrix지식/알고리즘 2023. 11. 7. 21:50
Given a m x n binary matrix mat, find the 0-indexed position of the row that contains the maximum count of ones, and the number of ones in that row.
In case there are multiple rows that have the maximum count of ones, the row with the smallest row number should be selected.
Return an array containing the index of the row, and the number of ones in it.
Example 1:
Input: mat = [[0,1],[1,0]]
Output: [0,1]
Explanation: Both rows have the same number of 1's. So we return the index of the smaller row, 0, and the maximum count of ones (1). So, the answer is [0,1].
Example 2:
Input: mat = [[0,0,0],[0,1,1]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So we return its index, 1, and the count. So, the answer is [1,2].
Example 3:
Input: mat = [[0,0],[1,1],[0,0]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So the answer is [1,2].
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] is either 0 or 1.{1의 개수가 가장 많고 가장 작은 행(i)의 인덱스 , 가장 많은 1의 개수} 를 리턴하면 된다.
class Solution { public int[] rowAndMaximumOnes(int[][] mat) { int m = mat.length; int n = mat[0].length; int max = 0; int index = 0; for(int i = 0; i < m; i++) { // 1 int count = 0; for(int j = 0; j < n; j++) { // 2 //if(mat[i][j] == 1) count += mat[i][j]; } if(count > max) { // 3 max = count; index = i; } } return new int[] {index, max}; // 4 } }
1. 각 행마다 모든 열의 1을 세기 위해 지역변수 count를 0으로 초기화하였다.
2. i번째 행의 모든 열의 1의 개수를 count에 누적시킨다.
(조건문을 써도 되지만 조건문을 쓰는 경우 동작속도가 1ms에서 4ms로 증가한다. 배열은 0과 1로만 이루어져있으니까 모든 열을 누적시켜도 똑같다.)
3. count > max 일때 1의개수(max)와 , 1의 개수가 가장 많이 들어있는 행의 index를 갱신한다.
(count >= max가 아니므로 동일한 1의 개수일 때 max가 동일할 때 더 큰 인덱스로 갱신하지 않는다. 그러므로 1의 개수가 가장 많은 인덱스 중 가장 작은 인덱스가 index 변수에 담긴다.)
4. 리턴한다.
https://leetcode.com/problems/row-with-maximum-ones
Row With Maximum Ones - LeetCode
Can you solve this real interview question? Row With Maximum Ones - Given a m x n binary matrix mat, find the 0-indexed position of the row that contains the maximum count of ones, and the number of ones in that row. In case there are multiple rows that ha
leetcode.com
'지식 > 알고리즘' 카테고리의 다른 글
50일 (733. Flood Fill) matrix (0) 2023.11.09 49일 (1582. Special Positions in a Binary Matrix) matrix (0) 2023.11.08 47일 (1572. Matrix Diagonal Sum) matrix 쉬움 (0) 2023.11.06 46일 (1260. Shift 2D Grid) matrix 참신함 (0) 2023.11.05 45일 (419. Battleships in a Board) matrix (0) 2023.11.04