第三週的最後一題是 Leftmost Column with at Least a One,就題目理解花了一下。

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]] Output: 1
題目給定一個排序好的二元陣列,找出最左邊有一的是哪一欄。因為已經排序好,所以只要記錄每一行最左邊的 1 是哪一欄,就可以只往右邊搜尋。
整體時間就只需要 O(N+M)
int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
vector<int> dim = binaryMatrix.dimensions();
int leftMostCol = dim[1];
for(int i=0; i<dim[0]; i++){
while(binaryMatrix.get(i, leftMostCol-1)){
leftMostCol--;
if(leftMostCol == 0)
return 0;
}
}
if(leftMostCol == dim[1])
return -1;
return leftMostCol;
}