順列リートコードソリューション


難易度 ミディアム
よく聞かれる Adobe Amazon (アマゾン) Apple アトラシアン ブルームバーグ ByteDance オークション Facebook ガレナ GoDaddyは ゴールドマン·サックス Google LinkedIn マイクロソフト オラクル Salesforce SAP ユーバー ヴイエムウェア ウォルマート・ラボ Yahoo
バックトラッキング

問題の順列リートコードソリューションは、整数の単純なシーケンスを提供し、完全なベクトルを返すように要求します。 配列 与えられたシーケンスのすべての順列の。 それで、問題を解決する前に。 順列に精通している必要があります。 したがって、順列は与えられた整数の配置に他なりません。 したがって、シーケンスのすべての順列が必要であると言うとき。 私たちは、与えられたシーケンスのすべての可能な配置を印刷または返却する必要があることを意味します。 理解を深めるために、いくつかの例を見てみましょう。

Given sequence: [1,2,3]
Permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

説明:1、2、3を順番に書き込むことができるすべての方法が出力として示されています。 順列で6、1、2を書くには合計3つの方法があります。

[0,1]
[[0,1],[1,0]]

説明:2、0を書き込む方法は1つしかありません。

順列Leetcodeソリューションのバックトラッキングアプローチ

順列リートコードソリューション

問題の順列Leetcodeソリューションは、指定されたシーケンスのすべての順列を生成するように要求しました。 一般に、順列を生成する必要があります。そうしないと、シーケンスの再帰が重要になります。 しかし、ここでは再帰またはバックトラックは少し注意が必要です。 XNUMXつの方法は、選択されていない要素から要素を選択し、それを回答の最後に配置することでした。 この方法で順列を生成し、どういうわけか、この順列が生成されたので、繰り返さないようにする必要があります。 しかし、これを行う代わりに、タスクを実行する簡単な方法を見つけようとします。 要素を選択して現在の要素と交換するとどうなりますか。 次に、再帰呼び出しを行って、現在のインデックスのXNUMXインデックス後にシーケンスのすべての順列を生成します。

順列の生成が完了したら、XNUMXインデックス先に進みます。 選択した要素を削除してから、別の要素を選択して手順を繰り返します。 このようにして、未使用の各要素を少なくともXNUMX回は現在の位置に配置したことを確認します。 そして、より小さなサブ問題を再帰的に呼び出したので。 小さなサブ問題は、現在のインデックスの直後から始まるシーケンスの順列を生成しています。 これらの順列を現在の順列に追加すると、現在のインデックスに設定された要素を使用して一連の順列が完成します。 このようにして、配列を左から右にトラバースし、問題をより小さなサブ問題に分割し続けます。 必要に応じて、可能な順列を生成し、それを回答に追加します。

バックトラックコード

順列LeetcodeソリューションのC ++コード

#include <bits/stdc++.h>
using namespace std;

void permutationUtil(vector<int> &nums, int i, int &numsSize, vector<vector<int>> &answer){
    if(i == numsSize){
        answer.push_back(nums);
    }
    for(int j = i; j < numsSize; j++){
        swap(nums[i], nums[j]);
        permutationUtil(nums, i+1, numsSize, answer);
        swap(nums[i], nums[j]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> answer;
    int numsSize = nums.size();
    permutationUtil(nums, 0, numsSize, answer);
    return answer;
}

int main(){
    vector<int> nums({1, 2, 3});
    vector<vector<int>> answer = permute(nums);
    for(auto i: answer){
        for(auto j: i)
            cout<<j<<" ";
        cout<<"\t";
    }
}
1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2

順列用JavaコードLeetcodeソリューション

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void permutationUtil(List<Integer> nums, int i, int numsSize, List<List<Integer>> answer){
        if(i == numsSize){
            answer.add(new ArrayList<Integer>(nums));
        }
        for(int j = i; j < numsSize; j++){
            Collections.swap(nums, i, j);
            permutationUtil(nums, i+1, numsSize, answer);
            Collections.swap(nums, i, j);
        }
    }
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new LinkedList();
        int numsSize = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<numsSize;i++)
            list.add(nums[i]);
        permutationUtil(list, 0, numsSize, answer);
        return answer;
    }
 
    public static void main(String[] args){
    	int nums[] = {1, 2, 3};
    	List<List<Integer>> answer = permute(nums);
    	System.out.println(answer.toString());
    }
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

複雑さの分析

時間の複雑さ

O(シグマ(P(N、K))、 ここで、Pはnのk順列または部分順列です。 より正式には、P(N、k)=(N!)/((Nk)!)。

スペースの複雑さ

オン!)、 Nであるすべての可能な解決策を保存する必要があるためです! サイズはNです。Nは配列のサイズです。