Matrix with value 0 and 1, find leftmost 1 column

高频的01矩阵找最左边1所在的列，假装没做过，分析了从O(m*n) 到O(m*logn)到O(m+n)的算法，最后实现。
0011111]], [0001111], [0111111]]。每row由0,1组成，前面全是0之后全是1，让找到最左边的1所在的列，这个例子里最左边的1是最后一行，在第二列。O(m+n)解法

lintcode----最左的1

第二题，一个01矩阵，每一行所有的0在前，1在后，要求给出矩阵中最左边的1所在的列id。我先给了一种O（m logn）的方法，面试官说我这个方法在n大的时候可以，然后直接告诉我了O（m+n）的方法让我实现，不知道算不算黑点。

题目描述： 
一个二维数组，每一行都只有0和1，前面部分是0，后一部分是1，找到数组里面所有行中最左边的1所在的列数。

注意事项： 
数组的行数，列数不超过1000 
为了约束时间复杂度，你的程序将会运行50000次

样例： 
给出 arr = [[0,0,0,1],[1,1,1,1]], 返回 0。

解释： 
arr[1][0]为所有行中最左边的1，其所在的列为0。 
给出 arr = [[0,0,0,1],[0,1,1,1]], 返回 1。

解释： 
arr[1][1]为所有行中最左边的1，其所在的列为1。

思路讲解：这个题目不是很难主要的难点就是关于程序会运行50000次，就说明程序会重复的调用，如果我们按照从第一列开始搜索、第二列搜索………….一直到最后一列。这样调用一次不会花费很多时间，但是如果这样的程序调用50000次，时间复杂度就变得很高了，所以我们就需要对这个数组特殊处理，因为我们每次都是判断是那一列，我们只需要将一整列加起来了，如果不是0，就说明其存在1，反之则不存在，这样时间复杂度就变成了o（n）。

代码详解:

class Solution {
public:
    /**
     * @param arr: The 2-dimension array
     * @return: Return the column the leftmost one is located
     */
    int getColumn(vector<vector<int>> &arr) {
        // Write your code here
        vector<int>res;
        i2D_change_1D(arr,res);
        for(int i=0;i<arr[0].size();i++){
            if(res[i]!=0){
                return i;
            }
        }

    }
    void i2D_change_1D(vector<vector<int>> arr,vector<int>&res){
        int m=arr.size();
        int n=arr[0].size();

        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=0;j<m;j++){
                sum=sum+arr[j][i];
            }
            res.push_back(sum);
        }
    }
};
--------------------- 
作者：一只叫羊的羊 
来源：CSDN 
原文：https://blog.csdn.net/qq_34355232/article/details/79668575 

版权声明：本文为博主原创文章，转载请附上博文链接！