C++で行列の対角要素を昇順にソートするプログラムの実装方法

n × m の行列 Mat が与えられたとき、左上から右下へ向かう各対角線（斜め方向）に沿って要素を昇順に並べ替えることを考えます。つまり、すべての対角線上の要素がそれぞれ独立にソートされた状態にします。

例えば、次のような入力行列があったとします。

この場合、出力される行列は次のようになります。

解決のためのアプローチ

この問題は「同じ対角線上にある要素を一度取り出してソートし、元の位置に書き戻す」というシンプルな発想で解決できます。具体的には、以下の手順に従います。

• solve() というメソッドを定義します。引数として対角線の開始位置 si、sj と行列 mat を受け取ります
• n := 行数、m := 列数 とします
• 一時的な配列 temp を用意します
• i := si、j := sj、index := 0 で初期化します
• i < n かつ j < m の間、次の処理を繰り返します
  • mat[i][j] の値を temp に追加し、i と j をそれぞれ 1 増やします
• temp 配列をソートします
• index := 0、i := si、j := sj に戻します
• i < n かつ j < m の間、次の処理を繰り返します
  • mat[i][j] := temp[index] とし、i、j、index をそれぞれ 1 増やします
• main メソッドでは、次の処理を行います
• n := 行数、m := 列数 とします
• i を 0 から n − 1 まで繰り返します
  • solve(i, 0, mat) を呼び出します（最初の列を起点とする対角線）
• j を 1 から m − 1 まで繰り返します
  • solve(0, j, mat) を呼び出します（最初の行を起点とする対角線）
• mat を返します

ポイントは、対角線の走査を「最初の列の各行」と「最初の行の各列」の 2 回のループで網羅できることです。これにより、行列内のすべての対角線を漏れなく処理できます。

計算量について

各対角線の長さは最大でも min(n, m) であるため、全体の時間計算量は O(n × m × log(min(n, m))) 程度になります。空間計算量は一時配列 temp の分だけ余分に必要ですが、対角線ごとに使い回すため O(min(n, m)) で抑えられます。

実装例

それでは、理解を深めるために実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << "[";
        for(int j = 0; j <v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    void solve(int si, int sj, vector < vector <int> > &mat){
        int n = mat.size();
        int m = mat[0].size();
        vector <int> temp;
        int i = si;
        int j = sj;
        int idx = 0;
        while(i < n && j < m){
            temp.push_back(mat[i][j]);
            i++;
            j++;
        }
        sort(temp.begin(), temp.end());
        idx = 0;
        i = si;
        j = sj;
        while(i < n && j < m){
            mat[i][j] = temp[idx];
            i++;
            j++;
            idx++;
        }
    }
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        for(int i = 0; i <n; i++){
            solve(i, 0, mat);
        }
        for(int j = 1; j < m; j++){
            solve(0, j, mat);
        }
        return mat;
    }
};
main(){
    vector<vector<int>> v = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
    Solution ob;
    print_vector(ob.diagonalSort(v));
}

入力

{{3,3,1,1},{2,2,1,2},{1,1,1,2}}

出力

[[1, 1, 1, 1], [1, 2, 2, 2], [1, 2, 3, 3]]

このように、solve() メソッドで対角線上の要素を収集・ソート・書き戻しし、diagonalSort() メソッドですべての対角線に対して solve() を適用することで、行列全体を対角方向に昇順ソートすることができました。