# 1428. Leftmost Column with at Least a One
###### tags: `Leetcode` `FaceBook` `Medium` `Binary Search`
Link: https://leetcode.com/problems/leftmost-column-with-at-least-a-one/
## 思路
一开始的想法是用col从后往前找，用map记录现在还valid的row，每次变化col，只看binaryMatrix[valid row][col]是否为1，如果不为1，证明该行前面也不会有1，该row不valid
debug了超级久，结果call get的次数还是超过了(**因为考虑最坏情况，他还是会把所有地方都get一遍**)

正确思路：binary search
## Code
## 正确思路

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        int res = 101;
        int rows = binaryMatrix.dimensions().get(0);
        int cols = binaryMatrix.dimensions().get(1);
        
        for(int i = 0;i < rows;i++){
            int start = 0;
            int end = cols-1;
            int mid;
            while(start<end){
                mid = (start+end)/2;
                if(binaryMatrix.get(i,mid)==1){
                    end = mid;
                }
                else{
                    start = mid+1;
                }
            }
            if(binaryMatrix.get(i,start)==1){
                res = Math.min(start,res);
            }
        }
        if(res == 101) return -1;
        return res;
    }
}

## 错误思路

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        List<Integer> dimension = binaryMatrix.dimensions();
        int rows = dimension.get(0);
        int cols = dimension.get(1);
        int colIndex = cols-1;
        for(int i = 0;i < rows;i++){
            map.put(i, 1);
        }
        
        boolean find = false;
        int validNum = rows;
        
        while(validNum != 0 && colIndex >= 0){
            for(Integer i: map.keySet()){
                System.out.println(i+" "+colIndex);
                if(find==false && map.get(i)==1 && binaryMatrix.get(i,colIndex)==1){
                    find = true;
                }
                else if(map.get(i)==1 && binaryMatrix.get(i,colIndex)==0){
                    map.put(i,0);
                    validNum--;
                }
            }
            colIndex--;
        }
        if(!find){
            return -1;
        }
        if(validNum == 0){
            return colIndex+2;
        }
        return colIndex+1;
    }
}