시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 설명
“정렬 된 행렬에서 음수 세기”문제에서 우리는 매트릭스 n 개의 행과 m 개의 열. 요소는 행 방향과 열 방향 모두 내림차순으로 정렬됩니다. 행렬의 총 음수 요소 수를 찾아야합니다.
예
grid = [[8,3,2,-1],[4,2,1,-1],[3,1,-1,-2],[-1,-1,-2,-3]]
8
설명 : 주어진 행렬에서 음수는 {-1, -1, -1, -2, -1, -1, -2, -3}입니다. 따라서 음수의 총 개수는 8입니다.
접근
접근 방식을 더 잘 이해하기 위해 더 나은 이해를 위해 동일한 예제를 사용하겠습니다. 주어진 행렬을 양수 및 음수 값 그 크기를 무시합니다. 따라서 주어진 행렬은 양수와 음수 값으로 변환됩니다.
따라서 행렬이 행 방향과 열 방향으로 내림차순으로 정렬된다는 것을 이미 알고 있습니다.이 문제를 해결하는 데 사용할 것입니다. 첫 번째 행에서 시작하여 순회를 시작합니다. 오른쪽에서 왼쪽으로 우리가 긍정적 인 요소를 만날 때까지 대장균의 뜻). 첫 번째 행의 총 음수 요소 수는 => m – col – 1이됩니다. 이제 다음 행으로 이동합니다. 여기에 요소가 정렬된다는 사실이 사용됩니다. matrix [0] [col]> = matrix [1] [col]의 값과 matrix [1] [col]의 모든 요소가 이보다 작기 때문에 col의 왼쪽에있는 요소를 순회 할 필요가 없습니다..
이제 matrix [1] [col]이 양수이면 첫 번째 행의 총 음수 요소 수는 => m – col – 1이됩니다. 그렇지 않으면 양수 요소를 만날 때까지 오른쪽에서 왼쪽으로 계속 이동합니다. 모든 행을 방문 할 때까지 다음 단계를 따릅니다. 모든 행의 최종 총 음수가 답이 될 것입니다.
암호
정렬 된 행렬 LeetCode 솔루션에서 음수 개수를 계산하는 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int count(vector<vector<int>>& grid)
{
int n=grid.size(),m=grid[0].size(), row=0, column=m - 1,ans=0;
while (row < n) {
while (column >= 0 && grid[row][column] < 0) column--;
ans += m - column - 1;
row++;
}
return ans;
}
int main()
{
vector<vector<int> > arr = { { 8,3,2,-1 },
{ 4,2,1,-1 },
{ 3,1,-1,-2 },
{ -1,-1,-2,-3 }};
cout<<count(arr)<<endl;
return 0;
}
8
정렬 된 행렬 LeetCode 솔루션에서 음수 개수를 계산하는 Java 코드
public class Tutorialcup {
public static int countNegatives(int[][] grid) {
int n=grid.length,m=grid[0].length, row=0, column=m - 1,ans=0;
while (row < n) {
while (column >= 0 && grid[row][column] < 0) column--;
ans += m - column - 1;
row++;
}
return ans;
}
public static void main(String[] args) {
int [][] grid = {
{8,3,2,-1},
{4,2,1,-1},
{3,1,-1,2},
{-1,-1-2,-3}
};
int ans= countNegatives(grid);
System.out.println(ans);
}
}
8
복잡성 분석
시간 복잡성
위 코드의 시간 복잡성은 O (n + m) 각 행과 최악의 경우 모든 열을 순회하고 있기 때문입니다. 여기서 n과 m은 각각 행 수와 열 수입니다.
공간 복잡성
위 코드의 공간 복잡성은 다음과 같습니다. O (1) 답을 저장하는 데 변수 만 사용하고 있기 때문입니다.
