Count Negative Numbers in a Sorted Matrix
给一个已经sorted的2d matrix, 求里面负数的个数. 这个题sorted肯定是要用二叉搜索的. 但是为了速度, 应该考虑两个情况,一个是里面全是负数, 一个数里面没有负数. 第一个情况是在第一个数就是负数的情况下, 第二个求你高考是在最后一个数是负数的情况下.
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;
}
}