Leetcode Leftmost Column with at Least a One

題目連結：​​Leftmost Column with at Least a One​​

題目大意：給你一個n*m的01矩陣，這個矩陣的每一行都是一個非遞減序列，要求你找到最前面的一列，這一列需要包括至少一個1

題目思路：首先根據非遞減的思想，我們可以很容易的想到，對于每一行最開始的1，我們可以用二分找到，如果每一行都找到了對應的初始1的列，那麼所有列最初始1的位置就可以找到了，代碼見解法一（對于找到最左邊的1，二分需要稍微的調整寫法），但是這個做法的複雜度是O（nlogm）。顯然這不是我們需要的線性複雜度。為了找到線性複雜度的解法，我們可以這樣做，由于我們需要找到最左邊的1的位置，而且對于一行單獨的序列，我們隻需要從右往左找，最後一個1就是我們需要的列，那麼如果是多個行呢？我們首先想到所有的1都是從右往左填充的，如果某個列值比我們目前找到的列值更小，那麼我們目前的列值找到該行時，這個行的目前列值也一定是1，如果目前列值對于某個行是0，那麼這個行一定不是我們要找的行，直接跳過即可，如果是1，那麼他可能是最優的，那麼不妨對該行，往前進行找1，那麼這樣我們就得到了一個解法：初始位置在右上角，碰到1往左找，碰到0往下找，那麼這樣我們得到的一定是最優的初始列值，這個解法的最壞情況也就是O（n+m），是一個線性的優秀解法，寫法也比二分寫法好寫，代碼見解法二

時間複雜度&&空間複雜度：O（n+m）&&O（1）

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *   public:
 *     int get(int x, int y);
 *     vector<int> dimensions();
 * };
 */

class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        vector<int>mat;
        mat = binaryMatrix.dimensions();
        int n = mat[0],m = mat[1];
        int minn = m;
        for(int i = 0;i < n;i++){
            int left = 0,right = m-1,mid,flag = 0;
            while(left <= right){
                mid = (left+right)/2;
                if(binaryMatrix.get(i,mid) == 1){                    
                    right = mid;
                    flag = 1;
                    if(left == right) break;
                }
                else{
                    left = mid+1;
                }
            }
            //cout<<"i == "<<i<<" right = "<<right<<" flag = "<<flag<<endl;
            if(flag == 1) minn = min(right,minn);
        }
        if(minn == m) return -1;
        else return minn;
    }
};      

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *   public:
 *     int get(int x, int y);
 *     vector<int> dimensions();
 * };
 */

class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        vector<int>mat;
        mat = binaryMatrix.dimensions();
        int n = mat[0],m = mat[1];
        int row = 0,column = m-1;
        while(row < n&&column >= 0){
            if(binaryMatrix.get(row,column) == 0) row++;
            else column--;
        }
        if(column == m-1) return -1;
        return column+1;
    }
};