第三週的最後一題是 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;
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料