arrays - 查找 1 数量最多的行

Question

给定一个 n x m 维的 bool 二维数组，其中每行都已排序。查找具有最大数量 1 的第一行的从 0 开始的索引。

下面是我写的代码

int rowWithMax1s(int arr[][], int n, int m) {
        int ans = -1;
        int row = 0;
        int col = m-1;
        while(row<n && col>=0){
            if(arr[row][col] == 1){
                col--;
                ans = row;
            }
            else{
                row++;
            }
        }
        return ans;
    }

我认为上述的时间复杂度是 O(M+N)。但它给我的时间限制超出了错误。

这是问题的链接 https://practice.geeksforgeeks.org/problems/row-with-max-1s0023/1#

请帮助我还可以做些什么来优化我的代码。

Answer 1

我很确定这不是你的错，而是驱动程序代码的错。

如果您提交几次，您可能会很幸运并被接受。我也尝试过这个:

class Solution {
    static int total = 0;
    int rowWithMax1s(int arr[][], int n, int m) {
        if ((total += n + m) > 300000)
            throw new RuntimeException("darn");
        ...
        (your actual solution)
        ...

经过几次尝试后被接受了。 300,000 个相对简单的 Java 步骤不可能花费超过 2 秒。

但是，如果您在代码编辑器中单击第 1 行，您会看到其驱动程序代码，该代码读取整个矩阵(或者更确切地说，对于所有测试用例，读取所有矩阵)。这很可能就是所有时间都去的地方。我们甚至不被允许编辑该部分。你可以尝试另一种语言。我用 Python 写了一个类似的解决方案，我提交了五次，它都被接受了。