Подсчет отрицательных чисел в решении LeetCode с отсортированной матрицей



LeetCode матрица

Постановка задачи

В задаче «Подсчитать отрицательные числа в отсортированной матрице» нам дается матрица из 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. Теперь перейдем к следующей строке. Здесь используется тот факт, что элементы отсортированы. Нам не нужно перемещаться по элементам, которые находятся слева от столбца, потому что значение матрицы [0] [col]> = matrix [1] [col] и всех элементов справа от матрицы [1] [col] меньше его..

Теперь, если матрица [1] [col] положительна, тогда общее количество отрицательных элементов в первой строке будет => m - col - 1, иначе мы продолжим обход справа налево, пока не встретим положительный элемент. Мы будем следовать этим шагам, пока не посетим все строки. Нашим ответом будет окончательное общее количество отрицательных чисел во всех строках.

Код:

Код C ++ для подсчета отрицательных чисел в решении LeetCode с отсортированной матрицей

#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

Код Java для подсчета отрицательных чисел в решении LeetCode с отсортированной матрицей

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) потому что мы используем только переменную для хранения ответа.

дело