C++で行列の各列の0の個数に基づいて列をソートし、インデックスを出力する方法

N行M列のサイズを持つ行列が与えられたとき、各列に含まれる0の個数を数え、その個数に基づいて列をソートし、ソート後の列のインデックスを出力するのが課題です。

例えば、1列目に0が1つ含まれ、2列目には0がまったく含まれず、3列目に0が2つ含まれている場合、0の少ない順に並べると出力は「2 1 3」になります。

入力例と出力例

Input:
    0 0 0
    1 1 1
    1 0 1
Output: 1 3 2

解説

上記の入力における各列の0の個数は次のとおりです。

• 1列目： 0が1個（1行目のみ）
• 2列目： 0が2個（1行目と3行目）
• 3列目： 0が1個（1行目のみ）

0の個数が少ない順に列を並べると「1 3 2」となり、これが出力されます。0の個数が同じ列が複数ある場合は、元のインデックスが小さい列が先に表示されます。

注意 − 行列のインデックスは1から始まるものとして扱います。

C++による実装

#include <bits/stdc++.h>
#define row 3
#define col 3
using namespace std;
void sorting(int arr[row][col]){
    vector<pair<int, int> >count_zero;
    for (int i = 0; i < col; i++){
        int count = 0;
        for (int j = 0; j < row; j++){
            if (arr[j][i] == 0)
                count++;
        }
        count_zero.push_back(make_pair(count, i));
    }
    sort(count_zero.begin(), count_zero.end());
    for (int i = 0; i < col; i++)
        cout<< count_zero[i].second + 1 << " ";
}
int main(){
    int array[row][col] = {
        { 0, 0, 0 },
        { 1, 1, 1 },
        { 1, 0, 1 }
    };
    cout<<"sorted order of zeroes count is : ";
    sorting(array);
    return 0;
}

アルゴリズムのポイント

• 0のカウント： 外側のループで各列を走査し、内側のループでその列の要素を確認して0の個数を数えます。
• pairの活用： vector<pair<int, int>> を使って「0の個数」と「列のインデックス」をペアで管理します。
• ソート処理： sort() 関数により、0の個数を第一優先、インデックスを第二優先として昇順にソートされます。
• 出力時の調整： インデックスは内部的に0始まりで保持しているため、出力時に+1して1始まりの番号として表示します。

計算量

全要素の走査にO(N×M)、ソートにO(M log M)が必要となるため、全体の計算量はO(N×M + M log M)です。

出力結果

このプログラムを実行すると、以下の出力が得られます。

sorted order of zeroes count is : 1 3 2