字节挂你的方式真的很独特。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近在网上看到一个帖子，一网友说面试字节聊了40分钟的项目，然后接雨水5分钟秒了，结果还是挂了。关于接雨水总共有两道题，一道是一维的，一道是二维的，这两道题被很多程序员认为是hard级别的，之前我们也都讲过，有兴趣的可以看下，，。

这两道题也是字节常考的题，在评论区有不少认证为字节的员工说，面试让你写hard题，基本代表要挂你了，这种挂人的方式真的很独特，面试不合适直接送走不就行了，结果人家5分钟做出来了，还是把人家给挂了。

我之前也面试过不少人，如果基本功不扎实会直接送走，如果能力还不错，就会出一道简单的算法题，但是算法不会作为重点考察的知识点，能不能做出来都不影响最终录取，因为对于大多数程序员来说，工作中算法基本上是用不到的，孰轻孰重我们不能本末倒置。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第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

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 100

• -100 <= grid[i][j] <= 100

问题分析

这题说的是统计矩阵中的所有负数，一种最简单的方式就是遍历矩阵中的所有元素，然后累加负数的个数。但这题说了，矩阵中的元素无论是按照行还是按照列都是递减的，也就是有序的，对于有序数组我们可以使用二分查找的方式来计算。

因为每行都是递减的，我们可以通过二分方式，查找每行中第一个负数的下标，如果该行没有负数，则返回该行的长度。那么该行中负数的个数就是 n 减去这个下标值，然后累加所有行的负数即可。

JAVA：

public int countNegatives(int[][] grid) {     int ans = 0;     int n = grid[0].length;     for (int[] nums : grid)         ans += n - binarySearch(nums);     return ans; } // 二分查找，返回第一个负数的下标，如果没有负数，则返回数组的长度。 private int binarySearch(int[] grid) {     int left = 0, right = grid.length;     while (left < right) {         int mid = (left + right) >> 1;         if (grid[mid] >= 0)             left = mid + 1;         else             right = mid;     }     return left; }

C++：

public:     int countNegatives(vector

 > &grid) {         int ans = 0;         int n = grid[0].size();         for (auto &nums: grid)             ans += n - binarySearch(nums);         return ans;     }     // 二分查找，返回第一个负数的下标，如果没有负数，则返回数组的长度。     int binarySearch(vector

 &grid) {         int left = 0, right = grid.size();         while (left < right) {             int mid = (left + right) >> 1;             if (grid[mid] >= 0)                 left = mid + 1;             else                 right = mid;         }         return left;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。