Leetcode題解 Python & C#：四月挑戰DAY21 Leftmost Column with at Least a One

給一個 BinaryMatrix 類別的物件，該物件有個由 0, 1 組成的二維串列屬性，要找出至少有個1的欄位最小索引，沒有則回傳-1。

該物件有兩個方法，一 get()，只能透過此方法去取得特定位置上的值。二 dimensions()，此方法會回傳列欄大小。

每列的值有經過排序(由小至大)。

如果呼叫 get() 超過1000次，也算失敗。

欄列的大小不超過100。

開始思考要如何找出目標值，除了每排有經過排序，但每欄並沒有提及。

因此除非知道每排最早出現 1 的位置，不然也暫時沒想到更好的方法。

get() 次數限制之下，每排要在 10 次內找出第一個 1 出現位置，最糟要在一百個已經排序的元素中搜查。

使用二分搜查法，50 > 25 > 13 > 7 > 4 > 2 > 1 ，最糟也能在七次內找到第一個 1 的位置。 萬一沒有，索引也會在等於欄數。這樣也能在限制內完成搜查。

Python

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        rows, cols = binaryMatrix.dimensions()
        memo = []
        for row in range(rows):
            l, r = 0 , cols
            while l < r:
                m = (r-l)//2 + l
                if binaryMatrix.get(row, m) == 0:
                    l = m + 1
                else:
                    r = m
            memo.append(r)
        return min(memo) if min(memo) < rows else -1

C#

class Solution {
    public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        int rows = binaryMatrix.Dimensions()[0];
        int cols = binaryMatrix.Dimensions()[1];
        // 使用 Binary search，取得每行上最小的1位置
        int minPos = cols;
        int r,m,l;
        for(int i = 0; i < rows; i++)
        {
            l = 0;
            r = cols;
            while(l < r)
            {
                m = (r-l)/2+l;
                if(binaryMatrix.Get(i,m)==0)
                {
                    l = m + 1;
                }
                else
                {
                    r = m;               
                }
                
            }
            minPos = r < minPos ? r: minPos;
        }      
        return minPos < cols ? minPos: -1;
    }
}