【LeetCode】 Leftmost Column with at Least a One

Description

(This problem is an interactive problem.)

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn't exist, return -1.

You can't access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

• BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
• BinaryMatrix.dimensions() returns a list of 2 elements [n, m], which means the matrix is n * m.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you're given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Constraints:

• 1 <= mat.length, mat[i].length <= 100
• mat[i][j] is either 0 or 1.
• mat[i] is sorted in a non-decreasing way.

(這是一個互動式問題)

一個二元陣列表示所有元素都是0或1。陣列中每一個個別的row都經過非遞減排序。

給一個row都排序過的二元陣列，回傳1再最左邊的column索引值(從零開始算)。如不存在任何1就回傳-1。

你不能直接存取二元陣列。你只能使用BinaryMatrix的interface去使用：

• BinaryMatrix.get(x, y)回傳位於(x, y)的元素(從零開始算)。
• BinaryMatrix.dimensions()回傳包含兩個元素[n, m]的list，代表該陣列大小為n * m。

使用了超過1000次的BinaryMatrix.get將被判定錯誤，並且任何試圖走後門的方式都會被取消資格。

為了方便測試，下面提供了四個陣列。你不能直接存取它們。

限制：

• 1 <= mat.length, mat[i].length <= 100
• mat[i][j] 只會是 0 或 1.
• mat[i] 會按照非遞減順序排列。

Example:

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0


Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1


Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1


Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Solution

• 先說，這題的x y給的感覺很奇怪，我一直搞反它們，因此這邊只講概念，下面的code雖然會過但請參考就好。
• 題目給的矩陣中，1一定在右邊，需要找到哪一排擁有最多的1(1在最左邊)。
• 最直覺的方法當然就是整個矩陣都給他看過去，然後包準你不會過。
• 比較省時間的方法是從最右上角開始跑：
  • 如果遇到1，往左走一格。
  • 如果遇到0，往下走一格。
  • 直到最下面為止結束。
• 最後要注意，最後會停在0的地方，因此答案要加一。
• 並且處理全為0的陣列，即可成功。

Code

/**
 * // 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> s = binaryMatrix.dimensions();
        int y = s[1] - 1;
        int x = 0;
        while(x < s[0] && y >= 0)
        {
            if(binaryMatrix.get(x, y) == 0)
                x++;
            else
                y--;
        }
        if(y + 1 == s[1]) return -1;
        return y + 1;
    }
};

tags: LeetCode C++