Problem#
給你一個 mxn 的二維陣列，每列是遞減排序(non-increasing order)，要你會傳總共有幾個負整數?
測資限制#
- $1 \le m,n \le 100$
想法#
最直覺就一個一個數: $O(n^2)$。
考慮對 m 行做二分搜，找第一個 < 0 的位置，因為陣列是遞減排序，所以找到第一個負數的位置，只要和 n 相減，就可以得到那行的負整數個數，最後加起來即可
- 時間複雜度: $\mathcal{O}(n\log{n})$
- 空間複雜度: $\mathcal{O}(1)$
AC Code#
我 m, n 跟題目的剛好寫相反XD
心得#
- 原本不知道(忘記ㄌ)
std::lower_bound或std::upper_bound可以支援遞減的陣列(descending)，寫出先 sort 的 $\mathcal{O}(n^2\log{n})$ :((