C++で解く対角トラバースII：リストのリストを対角順に出力する方法

問題の概要

「リストのリスト」である nums が与えられたとき、そのすべての要素を対角順（ダイアゴナルオーダー）に並べて出力するのがこの問題の目的です。

たとえば、次のような行ごとに長さの異なる配列（ジャグ配列）が入力として与えられた場合を考えてみましょう。

このとき、期待される出力は次のとおりです。

[1, 6, 2, 8, 7, 3, 9, 4, 12, 10, 5, 13, 11, 14, 15, 16]

解法のアプローチ

この問題は、各要素を「値と座標のセット」として一旦記録し、対角線ごとの順序になるようにソートし直すことで解けます。具体的な手順は以下の通りです。

• 結果を格納するための配列 ret を定義します。

• 一時的な2次元配列 v を定義します。

• すべての要素 nums[i][j] について、値と座標をまとめた { nums[i][j], i, j } を v の末尾に追加します。

• 配列 v をソートします。基準は「対角線の番号（i + j）が小さい順」。同じ対角線上に属する要素同士は、行番号 i が大きい方（より下側の要素）を先に並べます。

• ソート後の v の各要素について、先頭の値 it[0]（元の要素の値）を順に ret へ追加します。

• 最後に ret を返します。

なぜこのソート条件で正しい順序になるのか？

対角トラバースでは、i + j が等しい要素（同じ対角線上の要素）をまとめて処理し、対角線どうしは左上から右下へ向かって進みます。さらに、同一の対角線内では左下から右上の順に要素を訪れるため、行番号 i が大きい要素が先に来ます。比較関数 cmp は、まさにこのルールを実装したものです。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    static bool cmp(vector <int>& a, vector <int>& b ){
        int sum1 = a[1] + a[2];
        int sum2 = b[1] + b[2];
        return sum1 == sum2 ? a[1] > b[1] : sum1 < sum2;
    }
    vector<int> findDiagonalOrder(vector& nums) {
        vector<int> ret;
        vector<vector<int> > v;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums[i].size(); j++) {
                v.push_back({ nums[i][j], i, j });
            }
        }
        sort(v.begin(), v.end(), cmp);
        for (auto& it : v)
        ret.push_back(it[0]);
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}};
    print_vector(ob.findDiagonalOrder(v));
}

実行結果

入力

{{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}}

出力

[1, 6, 2, 8, 7, 3, 9, 4, 12, 10, 5, 13, 11, 14, 15, 16]

計算量の目安

全要素数を N とおくと、全要素を v に登録する処理に O(N)、ソートに O(N log N) の時間がかかります。したがって、全体の時間計算量は O(N log N) であり、補助的に O(N) のメモリが必要です。要素数が多い場合でも効率的に動作する、シンプルで実用的な解法といえます。