C++で1の個数が最大となるバイナリ行列の行番号を求める方法

この記事では、各行がソート済み（左側に0、右側に1が並ぶ）であるバイナリ行列が与えられたとき、1の個数が最も多い行の番号を求めるアルゴリズムを解説します。単純な全走査から二分探索、さらに最適化まで、段階的に改善できる3つのアプローチを紹介します。

問題の確認

まず、具体的な例で問題を理解しましょう。

入力

binMat[][] = {
    1, 1, 1, 1
    0, 0, 0, 0
    0, 0, 0, 1
    0, 0, 1, 1
}

出力

1

この例では、1行目（インデックス0）に4つの1が含まれているため、結果は「1」（1始まりの行番号）となります。

解法1：各行の1をカウントする単純な方法

最も直感的な解決策は、各行に含まれる1の総数を数え上げ、その中で最も多い行の番号を返すことです。時間計算量は O(R × C) です。

実装例

#include <iostream>
using namespace std;
#define R 4
#define C 4
int findMax1Row(bool mat[R][C]) {
    int max1Row = 0, max1Count = -1;
    int i, index;
    for (i = 0; i < R; i++) {
        int oneCount = 0;
        for(int j = 0; j < C; j++){
            if(mat[i][j])
                oneCount++;
        }
        if(oneCount > max1Count){
            max1Count = oneCount;
            max1Row = i;
        }
    }
    return (max1Row + 1);
}
int main() {
    bool mat[R][C] = {
        {0, 1, 1, 1},
        {0, 0, 1, 1},
        {0, 0, 0, 1},
        {0, 0, 0, 0}
    };
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
    return 0;
}

出力

The number of row with maximum number of 1's is 1

解法2：二分探索で最初の1の位置を見つける

各行がソートされていることを利用すると、二分探索によって「その行で最初に1が出現する位置」を効率よく見つけられます。行内の1の個数は「列数 − 最初の1のインデックス」で計算できます。この方法により、時間計算量を O(R log C) に抑えられます。

実装例

#include <iostream>
using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
    if(end >= start) {
        int mid = start + (end - start)/2;
        if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
            return mid;
        else if (arr[mid] == 0)
            return binarySearch1Row(arr, (mid + 1), end);
        else
            return binarySearch1Row(arr, start, (mid -1));
    }
    return -1;
}
int findMax1Row(bool mat[R][C]) {
    int max1Row = 0, max1Count = -1;
    int i, index;
    for (i = 0; i < R; i++) {
        index = binarySearch1Row(mat[i], 0, C-1);
        if (index != -1 && ( C-index) > max1Count) {
            max1Count = C - index;
            max1Row = i;
        }
    }
    return (max1Row + 1);
}
int main() {
    bool mat[R][C] = {
        {0, 1, 1, 1},
        {0, 0, 1, 1},
        {0, 0, 0, 1},
        {0, 0, 0, 0}
    };
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
    return 0;
}

出力

The number of row with maximum number of 1's is 1

解法3：探索範囲を絞り込む最適化

上記のアプローチにさらに最適化を加えることができます。前の行で見つかった「最初の1のインデックス」を利用し、現在の行がそれより多くの1を含むかどうかを先に判定します。1の数が上回る可能性がある場合のみ二分探索を実行し、その際の探索範囲も「0 〜 前の行の最初の1のインデックス」までに限定します。

これにより、現在の記録よりも1の少ない行に対する無駄な計算を省き、処理のオーバーヘッドを大幅に削減できます。

実装例

#include <iostream>
using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
    if(end >= start) {
        int mid = start + (end - start)/2;
        if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
            return mid;
        else if (arr[mid] == 0)
            return binarySearch1Row(arr, (mid + 1), end);
        else
            return binarySearch1Row(arr, start, (mid -1));
    }
    return -1;
}
int findMax1Row(bool mat[R][C]) {
    int i, index;
    int max1Row = 0;
    int max1Count = binarySearch1Row(mat[0], 0, C - 1);
    for (i = 1; i < R; i++){
        if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) {
            index = binarySearch1Row (mat[i], 0, C - max1Count);
            if (index != -1 && C - index > max1Count) {
                max1Count = C - index;
                max1Row = i;
            }
        }
        else
        max1Count = binarySearch1Row(mat[i], 0, C - 1);
    }
    return (max1Row + 1);
}
int main() {
    bool mat[R][C] = {
        {0, 1, 1, 1},
        {0, 0, 0, 1},
        {0, 0, 1, 1},
        {0, 0, 0, 0}
    };
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
    return 0;
}

出力

The number of row with maximum number of 1's is 1

まとめ：各解法の計算量比較

本記事で紹介した3つのアプローチの計算量は以下のとおりです。

• 解法1（全要素のカウント）：O(R × C)
• 解法2（二分探索）：O(R log C)
• 解法3（探索範囲の絞り込み）：最悪時 O(R log C)。ただし探索範囲が狭まるため、実際には平均的により高速に動作します。

行列のサイズが大きい場合は、二分探索ベースの解法2や解法3を採用することで、パフォーマンスを大きく向上させることができます。