Facebook电面

面试官是华人小美女，很nice~
题目是一个包含0和1的matrix，大概是这样[[0 1 1 1], [0 0 0 1]

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

一次电面，还是太紧张了，最后很多corner case没写好。

楼主，这题是不是每次对中间那一列进行线性扫描，如果发现1就然后继续在左侧的列中寻找；否则就在右侧的列中寻找；复杂度是row*log(col)

写了一个，大家看看有没有问题，求加点米~~
#include <vector>
#include <iostream>
using namespace std;

int leftMostColumn(vector<vector<int> >& nums) {
        int row = nums.size();
        if (row==0||nums[0].size()==0||nums[0].size()==1)
                return -1;
        int col = nums[0].size();
        int i = 0;
        int j = col-1;
        while (i<=j) {
                int mid = i+(j-i)/2;
                bool flag = false;
                for (int k = 0; k<row; ++k) {
                        if (nums[k][mid]==1) {
                                flag = true;
                                break;
                        }
                }
                if (flag) {
                        j = mid-1;
                }
                else {
                        i = mid+1;
                }
        }
        if (i==0)
                return -1;
        return i;
}

int main() {
        vector<vector<int> > nums;
        nums.push_back(vector<int>{0, 0, 1, 1});
        nums.push_back(vector<int>{0, 0, 0, 1});
        nums.push_back(vector<int>{0, 0, 1, 1});
        nums.push_back(vector<int>{0, 0, 0, 0});
        cout << leftMostColumn(nums) << endl;
        return 0;
}

从右上开始找 复杂度可以优化到 O(row + col)

daidaixiong 发表于 2018-12-8 15:01
楼主，这题是不是每次对中间那一列进行线性扫描，如果发现1就然后继续在左侧的列中寻找；否则就在右侧的列 ...

是哈，针对每一行使用binary search，复杂度就是row*log(col)，要注意考虑某一行全零和整个matrix全零的情况

uggl233 发表于 2018-12-9 06:04
从右上开始找 复杂度可以优化到 O(row + col)

哇，谢谢指点，具体怎么操作呢？

wangyandan418 发表于 2018-12-9 06:38
哇，谢谢指点，具体怎么操作呢？

就从右上方开始找呀 如果是0的话 就往下走 说明这一行没什么好研究的了 如果是1的话 说明是potential col 就往左走咯一直走到底为0后然后再往下看 这算法很intuitive吧.. 老哥你纸上画一下就知道了

wangyandan418 发表于 2018-12-9 06:38
哇，谢谢指点，具体怎么操作呢？

有帮助的话 加个米哈哈

uggl233 发表于 2018-12-9 14:30
就从右上方开始找呀 如果是0的话 就往下走 说明这一行没什么好研究的了 如果是1的话 说明是potential col ...

谢谢你啊!

#include <vector>
#include <iostream>
using namespace std;

int leftMostColumn(vector<vector<int> >& nums) {
    int res = nums[0].size();
    for(int i = 0; i< nums.size(); i++){
        int l = 0, r = nums[i].size() - 1;
        while(l+1<r){
            int mid = l + (r-l)/2;
            if(nums[i][mid] == 1){
                r = mid;
            }else{
                l = mid;
            }
        }
        if(nums[i][l] == 1){
            res = min(l, res);
        }else if(nums[i][r] == 1){
            res = min(r, res);
        }
    }

    return res;
}

int main() {
    vector<vector<int> > nums;
    nums.push_back(vector<int>{0, 0, 1, 1});
    nums.push_back(vector<int>{0, 0, 0, 1});
    nums.push_back(vector<int>{0, 0, 1, 1});
    nums.push_back(vector<int>{1, 1, 1, 1});
    cout << leftMostColumn(nums) << endl;
    return 0;
}
O(m*log(n))的时间复杂度算法 有帮助的话加个米 也能写一个O(m+n)的算法