--- title: 1351. Count Negative Numbers in a Sorted Matrix tags: leetcode,解題報告 --- # 1351. Count Negative Numbers in a Sorted Matrix 題目連結: [Leetcode](https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/description/) ## 題目概要 給一 $n\times m$ 的已排序陣列 輸出共有多少個負數 ## 想法 ### 法一 暴力解 迭代每一個數值 每迭代到一個負數就紀錄 ### 法二 二分搜 針對每列陣列做二分搜尋,找到負數的開頭索引值 ### 法三 線性搜尋 因陣列的負數在整個$n\times m$集中在右下測 且每列皆已排序 因此可從每列的後方開始尋找負數的開頭索引值 找到一列的值後紀錄該列的負數數量 再往下一列的同個索引值開始向左尋找 直到索引值 $<$ 0 ## 參考解法 歡迎補充 :::spoiler CPP 暴力解 ```cpp= int countNegatives(vector<vector<int>>& grid) { int ans = 0; for (int i=0; i<grid.size(); i++){ for (int j=0; j<grid[0].size(); j++){ if (grid[i][j] < 0) ans++; } } return ans; } ``` ::: :::spoiler CPP 二分搜 ```cpp= int countNegatives(vector<vector<int>>& grid) { int ans = 0, n = grid[0].size(); for (auto r: grid){ int left = 0, right = n-1, mid; while (left <= right){ mid = (left + right) / 2; if (r[mid] < 0) right = mid -1; else left = mid +1; } ans += n - left; } return ans; } ``` ::: :::spoiler CPP 線性搜 ```cpp= int countNegatives(vector<vector<int>>& grid) { int ans = 0, n = grid[0].size(), index = n - 1; for (auto r: grid){ while (index >= 0 and r[index] < 0){ index--; } ans += n - (index + 1); } return ans; } ``` :::