LeetCode-Algorithms-[Easy][双百解法]1351. 统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。

请你统计并返回 grid 中 负数 的数目。

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵*有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]
输出：0

示例 3：

输入：grid = [[1,-1],[-1,-1]]
输出：3

示例 4：

输入：grid = [[-1]]
输出：1

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

最优解：倒序遍历

利用行列都非递增的性质，可以按行或按列遍历,官方题解给的复杂度我并不算完全赞同，我认为这个的复杂度应该为O(m+n)

    public int countNegatives(int[][] grid) {
        int  n = grid[0].length;
        int j = n - 1;
        int sum = 0;
        for (int[] column : grid) {
            while (j >= 0 && column[j] < 0) {
                j--;
            }
            sum += n - j - 1;
        }
        return sum;
    }

在此基础上的优化：二分查找

    public int countNegatives_BinarySearch(int[][] grid) {
        int n = grid[0].length;
        int sum = 0;
        int l = 0;
        int h = n - 1;
        for (int[] column : grid) {
            while (l < h) {
                int mid = l + ((h - l) >> 1);
                if (column[mid] >= 0) {
                    l = mid + 1;
                } else {
                    h = mid;
                }
            }
            if (column[l] < 0) {
                sum += n - l;
            }
            h = l;
            l = 0;
        }
        return sum;
    }

这个方法还能不能优化，实际上是可以的。因为m与n是有可能一个比另一个长的，我们保证拿比较大的那个数来进行二分，可以继续降低这个算法的时间复杂度

    public int countNegatives_BinarySearch_2(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (m > n) {
            return getSumWithLongerM(grid);
        }
        return getSumWithLongerN(grid);
    }

    private int getSumWithLongerM(int[][] grid) {
        int m = grid[0].length;
        int sum = 0;
        int l = 0;
        int h = m - 1;
        for (int[] row : grid) {
            while (l < h) {
                int mid = l + ((h - l) >> 1);
                if (row[mid] >= 0) {
                    l = mid + 1;
                } else {
                    h = mid;
                }
            }
            if (row[l] < 0) {
                sum += m - l;
            }
            h = l;
            l = 0;
        }
        return sum;
    }

    private int getSumWithLongerN(int[][] grid) {
        int n = grid[0].length;
        int sum = 0;
        int l = 0;
        int h = n - 1;
        for (int[] column : grid) {
            while (l < h) {
                int mid = l + ((h - l) >> 1);
                if (column[mid] >= 0) {
                    l = mid + 1;
                } else {
                    h = mid;
                }
            }
            if (column[l] < 0) {
                sum += n - l;
            }
            h = l;
            l = 0;
        }
        return sum;
    }