每行有序布尔二维数组找含最多1的首行，O(n+m)代码超时如何优化

给定n行m列、每行有序排列的布尔二维数组，目标是找出含1数量最多的行的0-based下标。

原代码超时原因分析 #

你的代码理论时间复杂度确实是O(n+m)，但超时的核心原因是内存访问模式不符合CPU缓存的行优先规则：你的代码交替跨行、跨列访问元素，缓存命中率极低，实际运行耗时远高于理论复杂度计算值，遇到大规模测试用例就会触发时间超限。

优化方案 #

方案1：每行二分查找第一个1的位置（推荐，实测性能更稳定） #

利用每行有序的特性，对每一行二分查找第一个出现1的下标，该行的1的数量为m - 第一个1的下标，记录最大值对应的行号即可。时间复杂度为O(n log m)，因为每行是连续访问，CPU缓存命中率高，大多数测试场景下实际运行速度优于*O(n+m)*的跳跃访问实现。
实现代码如下：

int rowWithMax1s(int arr[][], int n, int m) {
    int max_cnt = 0;
    int ans = -1;
    for(int i = 0; i < n; i++) {
        // 二分找当前行第一个1的位置
        int left = 0, right = m-1;
        int first_one = m;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(arr[i][mid] == 1) {
                first_one = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int cnt = m - first_one;
        if(cnt > max_cnt) {
            max_cnt = cnt;
            ans = i;
        }
    }
    return ans;
}

方案2：优化原O(n+m)逻辑的访问效率 #

如果要保留*O(n+m)*的理论复杂度，可以在原有逻辑基础上减少不必要的边界判断，同时利用连续访问提升缓存命中率：

int rowWithMax1s(int arr[][], int n, int m) {
    int ans = -1;
    int col = m - 1;
    for(int row = 0; row < n && col >= 0; row++) {
        // 连续向左找当前行最左的1，减少跨行次数
        while(col >= 0 && arr[row][col] == 1) {
            col--;
            ans = row;
        }
    }
    return ans;
}

这个版本把原有的单次判断改成内层连续向左查找，减少了循环判断的次数，同时同一行的连续访问也提升了缓存命中率，性能比原有实现高很多。

内容的提问来源于stack exchange，提问作者Vivek Kumar