C++で循環配列のループ(閉路)を検出するアルゴリズムと実装例

正と負の整数値から構成される循環配列 nums を想定します。あるインデックスに格納された数値 k が正の数であれば、前方向に k ステップ移動し、負の数(−k)であれば、後ろ方向に k ステップ移動します。配列は循環しているため、最後の要素の「次」は最初の要素となり、最初の要素の「前」は最後の要素となります。このとき、配列 nums の中にループ(閉路)が存在するかどうかを判定するのが本問題です。

有効な閉路は、同一のインデックスで開始・終了し、長さが 1 より大きいものでなければなりません。たとえば入力が [2,-1,1,2,2] の場合、インデックス 0 → 2 → 3 → 0 という長さ 3 の閉路が存在するため、出力は true になります。

解法のアプローチ

この問題は、連結リストの閉路検出で有名なフロイドの循環検出法(ウサギとカメのアルゴリズム)を応用することで効率的に解けます。slow(遅い)ポインタと fast(速い)ポインタを用意し、slow は 1 ステップずつ、fast は 2 ステップずつ進めます。両者が同じ位置に到達すれば閉路が存在すると判断できます。さらに、探索済みの経路は 0 で上書きしてマークすることで、同じ経路を再調査する無駄を省き、全体の計算量を O(n) に抑えています。

アルゴリズムの手順

• n を nums のサイズとする。
• n < 2 の場合は false を返す(要素が 1 つでは長さ 2 以上の閉路は作れないため)。
• i = 0 から n−1 まで、各要素に nums[i] := nums[i] mod n を適用し、移動量を正規化する。
• i = 0 から n−1 まで以下を繰り返す:
  
  • nums[i] == 0 の場合は既に訪問済みなので、次の反復へ continue する。
  • slow = i、fast = i として初期化する。
  • 「nums[slow] × nums[fast] > 0」かつ「nums[next(fast)] × nums[slow] > 0」の間(= 移動方向が一致している間)、以下を繰り返す:
    
    • slow を next(slow) へ 1 ステップ進める。
    • fast を next(next(fast)) へ 2 ステップ進める。
    • slow == fast になった場合:
      
      • slow == next(slow)(自分自身へ戻る長さ 1 の閉路)ならば、while ループを抜ける。
      • そうでなければ true を返す。
  • x := nums[i]、slow := i とする。
  • nums[slow] × x > 0 の間(= 同じ方向の経路上である限り)、以下を繰り返す:
    
    • temp := next(slow) を保存する。
    • nums[slow] := 0 として訪問済みマークを付ける。
    • slow := temp とする。
• すべての開始点を試しても閉路が見つからなければ false を返す。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int next(vector<int>& nums, int i){
        int n = nums.size();
        return (n+nums[i]+i)%n;
    }
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return false;
        for(int i = 0; i < n; i++)nums[i] %= n;
        for(int i = 0; i < n; i++){
            if(nums[i] == 0) continue;
            int slow = i;
            int fast = i;
            while(nums[slow] * nums[fast] > 0 && nums[next(nums, fast)] * nums[slow] > 0){
                slow = next(nums, slow);
                fast = next(nums, next(nums, fast));
                if(slow == fast){
                    if(slow == next(nums, slow))
                    break;
                    return true;
                }
            }
            int x = nums[i];
            slow = i;
            while(nums[slow] * x > 0){
                int temp = next(nums, slow);
                nums[slow] = 0;
                slow = temp;
            }
        }
        return false;
    }
};
main(){
    vector<int> v = {2,-1,1,2,2};
    Solution ob;
    cout << (ob.circularArrayLoop(v));
}

入力

[2,-1,1,2,2]

出力

1