專欄：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算法文檔 。