今天在Youtube上看到這么一道題旭寿， 我之前肯定是有見過的，但是忘了是怎么做的陈肛。
Count Negative Integers
Array is sorted.
例子：
?[-3, -2, -1, 1]? -->3
[-2, 2, ,3,, 4] -->1
[4,? 5 , 7,? 8] -->0
一共4 個(gè)。
O(nm) is naive solution
最暴力的解法就是整個(gè)matrix走一遍巩检，看看一共幾個(gè)non-negative numbers.
注意Each row/col is sorted.
我本來的優(yōu)化想法是每一行橫著走，看到第一個(gè)non-negative 停下來去下一行。但是這個(gè)做法沒有利用到col sorted 的用處。
視頻里的solution是從第一行的最后一個(gè)元素開始走奏夫，直到碰到倒數(shù)第一個(gè)negative number.這時(shí)候，馬上切換到下一行历筝。如果這個(gè)數(shù)字是個(gè)負(fù)數(shù)酗昼，繼續(xù)切換到下一行，知道col上我們到達(dá)一個(gè)non-negative number,這時(shí)候再往左邊開始走梳猪。 這個(gè)解法的核心是麻削，由于matrix已經(jīng)排序好了，所以在row上春弥，碰到了倒數(shù)第一個(gè)negative后呛哟，我們知道這個(gè)數(shù)的左邊全部是negative，不用再看了匿沛。 在col上扫责，碰到第一個(gè)non-negative后，我們知道col再往下同一個(gè)col不會(huì)再出現(xiàn)negative了俺祠，這個(gè)時(shí)候就應(yīng)該往左開始走公给。【*注： 我們往next-col走的前提是蜘渣，我們?cè)谶@個(gè)row發(fā)現(xiàn)了第一個(gè)negative number, 這樣我們既可以添加上 這一行的negative 數(shù)量， 又可以跳到下一行肺然。 如果row上連第一個(gè)negative number都沒找到蔫缸，我們立刻就到下一個(gè)col也沒什么意義，因?yàn)橄乱粋€(gè)col這個(gè)位置由于sort也是正數(shù)】
count = col+1 這個(gè)太恐怖了际起。拾碌。吐葱。我本來還想拿col 去減left most col. 但是這特么不就是col-0+1=col+1嗎。校翔。
知道了算法弟跑，大部分人也許還是會(huì)寫一個(gè)double loop。但是optimal應(yīng)該用一個(gè)loop就可以解決防症。
