專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
最近在網(wǎng)上看到一個(gè)帖子，一網(wǎng)友說面試字節(jié)聊了40分鐘的項(xiàng)目，然后接雨水5分鐘秒了，結(jié)果還是掛了。關(guān)于接雨水總共有兩道題，一道是一維的，一道是二維的，這兩道題被很多程序員認(rèn)為是hard級(jí)別的，之前我們也都講過，有興趣的可以看下，，。
這兩道題也是字節(jié)?？嫉念}，在評(píng)論區(qū)有不少認(rèn)證為字節(jié)的員工說，面試讓你寫hard題，基本代表要掛你了，這種掛人的方式真的很獨(dú)特，面試不合適直接送走不就行了，結(jié)果人家5分鐘做出來了，還是把人家給掛了。
我之前也面試過不少人，如果基本功不扎實(shí)會(huì)直接送走，如果能力還不錯(cuò)，就會(huì)出一道簡單的算法題，但是算法不會(huì)作為重點(diǎn)考察的知識(shí)點(diǎn)，能不能做出來都不影響最終錄取，因?yàn)閷?duì)于大多數(shù)程序員來說，工作中算法基本上是用不到的，孰輕孰重我們不能本末倒置。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1351題：統(tǒng)計(jì)有序矩陣中的負(fù)數(shù)，難度是簡單。
給你一個(gè) m * n 的矩陣 grid，矩陣中的元素?zé)o論是按行還是按列，都以非嚴(yán)格遞減順序排列。 請(qǐng)你統(tǒng)計(jì)并返回 grid 中負(fù)數(shù)的數(shù)目。
示例1：
輸入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] 輸出：8 解釋：矩陣中共有 8 個(gè)負(fù)數(shù)。
示例2：
輸入：grid = [[3,2],[1,0]] 輸出：0
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
問題分析
這題說的是統(tǒng)計(jì)矩陣中的所有負(fù)數(shù)，一種最簡單的方式就是遍歷矩陣中的所有元素，然后累加負(fù)數(shù)的個(gè)數(shù)。但這題說了，矩陣中的元素?zé)o論是按照行還是按照列都是遞減的，也就是有序的，對(duì)于有序數(shù)組我們可以使用二分查找的方式來計(jì)算。
因?yàn)槊啃卸际沁f減的，我們可以通過二分方式，查找每行中第一個(gè)負(fù)數(shù)的下標(biāo)，如果該行沒有負(fù)數(shù)，則返回該行的長度。那么該行中負(fù)數(shù)的個(gè)數(shù)就是 n 減去這個(gè)下標(biāo)值，然后累加所有行的負(fù)數(shù)即可。
JAVA：
public int countNegatives(int[][] grid) { int ans = 0; int n = grid[0].length; for (int[] nums : grid) ans += n - binarySearch(nums); return ans; } // 二分查找，返回第一個(gè)負(fù)數(shù)的下標(biāo)，如果沒有負(fù)數(shù)，則返回?cái)?shù)組的長度。 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; } // 二分查找，返回第一個(gè)負(fù)數(shù)的下標(biāo)，如果沒有負(fù)數(shù)，則返回?cái)?shù)組的長度。 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; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼