Count Negative Numbers in a Sorted Matrix
给一个已经sorted的2d matrix, 求里面负数的个数. 这个题sorted肯定是要用二叉搜索的. 但是为了速度, 应该考虑两个情况,一个是里面全是负数, 一个数里面没有负数. 第一个情况是在第一个数就是负数的情况下, 第二个求你高考是在最后一个数是负数的情况下.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public int countNegatives(int[][] grid) { int res = 0; for(int[] g : grid){ res += find(g); } return res; } private int find(int[] nums) { int left = 0 ; int right = nums.length - 1; if(nums[right] >= 0) return 0; if(nums[left] < 0) return nums.length; while(left <= right) { int mid = left + (right - left) / 2; if(nums[mid] < 0) right = mid - 1; else left = mid + 1; } return nums.length - left; } } |