排列Leetcode解決方案  


難度級別 中烘焙
經常問 土磚 亞馬遜 蘋果 Atlassian的 彭博社 ByteDance 易趣 Facebook Top本 GoDaddy的 高盛 谷歌 LinkedIn Microsoft微軟 神諭 Salesforce的 SAP 尤伯杯 VMware的 沃爾瑪實驗室 雅虎
算法 回溯 編碼 訪問 面試準備 力碼 力碼解決方案

問題“排列Leetcode解決方案”提供了一個簡單的整數序列,並要求我們返回完整的向量或 排列 給定序列的所有排列。 因此,在解決問題之前。 我們應該熟悉排列。 因此,排列只是給定整數的排列。 因此,當我們說需要序列的所有排列時。 我們的意思是要求我們打印或返回給定序列的所有可能排列。 讓我們看一些示例以更好地理解。

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。

排列Leetcode解決方案的回溯方法  

排列Leetcode解決方案

問題排列Leetcode解決方案要求我們生成給定序列的所有排列。 通常,我們需要生成一個排列,否則某些序列遞歸是關鍵。 但是這裡的遞歸或回溯有些棘手。 一種方法可能是從未選擇的元素中選擇一個元素並將其放在答案的末尾。 這種方式會產生排列,並以某種方式確保記住該排列已生成並且不應重複。 但是,我們沒有這樣做,而是嘗試找到一種簡單的方法來執行任務。 如果我們選擇一個元素並將其與當前元素交換該怎麼辦。 然後進行遞歸調用,以生成當前索引之後的一個索引序列的所有排列。

也可以看看
合併兩個排序的鍊錶

一旦我們完成了生成排列的操作,前面的一個索引就可以了。 我們刪除選擇的元素,然後選擇另一個元素並重複該過程。 這樣,我們確保將每個未使用的元素至少放置一次在當前位置。 而且由於我們遞歸調用了一個較小的子問題。 較小的子問題正在生成從當前索引之後開始的序列的排列。 將這些排列添加到當前排列可以完成一組排列,並在當前索引處設置一個元素。 這樣,我們就可以從左到右遍歷數組,並將問題分成較小的子問題。 一旦滿足需要,我們就生成了可能的排列並將其添加到答案中。

回溯代碼  

排列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

用於置換Leetcode解決方案的Java代碼

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)!)。

也可以看看
通過反轉子陣列Leetcode解決方案使兩個陣列相等

空間複雜度

上!), 因為我們必須存儲所有可能的解決方案N! 大小,其中N是數組的大小。