脸书店面

一个白人小哥，出了一道九章算法的刷题网（也是L开头）的原题 把就拔（

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

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

小哥说好，没让写了。尬聊了一阵就结束了

ccjobhunter2011 发表于 2018-4-8 23:57
public int getColumn(int[][] arr) {
        // Write your code here
        int n =  arr.length; ...

支持。虽然代码好像有typo过不了。思路没错。

我改了C++

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param arr: The 2-dimension array
   
5.      * @return: Return the column the leftmost one is located
   
6.      */
   
7.     int getColumn(vector<vector<int>> &arr) {
   
8.         // Write your code here
   
9.         int n = arr.size();
   
10.         int m = arr[0].size();
    
11.         int ans = 0;
    
12.         for (int i = 0; i < m; i++) {
    
13.             if (arr[0][i]) {
    
14.                 ans = i;
    
15.                 break;
    
16.             }
    
17.         }
    
18.         
    
19.         for (int i = 1; i < n; i++) {
    
20.             if (arr[i][ans] == 0) continue;
    
21.             while (ans > 0 && arr[i][ans - 1] == 1)
    
22.                 ans--;
    
23.         }
    
24.         return ans;
    
25.     }
    
26. };
    
27. 
    

复制代码

chipmonk 发表于 2018-4-8 23:39
你这样worst case o(mn)

public int getColumn(int[][] arr) {
        // Write your code here
        int n =  arr.length;
        int m = arr[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            if (arr[0][i] == 1) {
                ans = i;
                break;
            }
        }
        for (int i = 1; i < n; i++) {
            if (arr[i][ans] == 0) {
                continue;
            }
            while (ans > 0 && arr[i][ans - 1] == 1) {
                ans--;
            }
        }
        return ans;
    }

只需要keep 一个index , 每一行从index往前找，直到不是1 . 这样一共就只扫了一遍 m = number of cols.

1. public class Solution {
   
2.     /**
   
3.      * @param arr: The 2-dimension array
   
4.      * @return: Return the column the leftmost one is located
   
5.      */
   
6.     public int getColumn(int[][] arr) {
   
7.         // Write your code here
   
8.         if (arr.length == 0) return -1;
   
9.         int m = arr.length;
   
10.         int n = arr[0].length;
    
11.         int k = arr[0].length - 1;
    
12.         
    
13.         for (int i = 0 ; i < m ; i ++) {
    
14.             int[] row = arr[i];
    
15.             while (k >= 0 && row[k] == 1) { k --; }
    
16.         }
    
17.         return k + 1;
    
18.     }
    
19.    
    
20.     private int BS(int [] arr) {
    
21.         int s = 0;
    
22.         int e = arr.length - 1;
    
23.         while (s + 1 < e) {
    
24.             int m = s + (e - s) / 2;
    
25.             if (arr[m] == 0) s = m;
    
26.             else e = m;
    
27.         }
    
28.         if (arr[s] == 1) return s;
    
29.         else if (arr[e] == 1) return e;
    
30.         else return arr.length;
    
31.     }
    
32. }

复制代码

赞赞赞多谢楼主贡献面经

谢谢分享，就是拿到找罪左边一的提，哈哈哈

Rlogc 最优解？

chipmonk 发表于 2018-4-8 13:02
Rlogc 最优解？

n + m 最优

chipmonk 发表于 2018-4-8 13:02
Rlogc 最优解？

int left = matrix[0].length;
for (int i = 0; i < matrix.length; i++)
    for (int j = 0; j < left; j++) {
          if (matrix[i][j] == 1) {
                 left = j;
                 break;
          }
    }
    return left;
}

求加米

你可能面的不是sde否则这样肯定挂

你这样worst case o(mn)

chipmonk 发表于 2018-4-8 23:39
你这样worst case o(mn)

嗯嗯。jiuzhang O（m+n）