정렬 된 행렬 LeetCode 솔루션에서 음수 세기


알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 매트릭스조회수 32

문제 설명

“정렬 된 행렬에서 음수 세기”문제에서 우리는 매트릭스 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입니다.

접근

접근 방식을 더 잘 이해하기 위해 더 나은 이해를 위해 동일한 예제를 사용하겠습니다. 주어진 행렬을 양수 및 음수 값 그 크기를 무시합니다. 따라서 주어진 행렬은 양수와 음수 값으로 변환됩니다.

정렬 된 행렬에서 음수를 계산하는 leetcode 솔루션

따라서 행렬이 행 방향과 열 방향으로 내림차순으로 정렬된다는 것을 이미 알고 있습니다.이 문제를 해결하는 데 사용할 것입니다. 첫 번째 행에서 시작하여 순회를 시작합니다. 오른쪽에서 왼쪽으로 우리가 긍정적 인 요소를 만날 때까지 대장균의 뜻). 첫 번째 행의 총 음수 요소 수는 => 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) 답을 저장하는 데 변수 만 사용하고 있기 때문입니다.

참조

코멘트를 남겨

Translate »