排列Leetcode解决方案  


难度级别 中等
经常问 土砖 亚马逊 Apple Atlassian的 彭博 ByteDance 易趣 Facebook Top本 GoDaddy的 高盛 谷歌 LinkedIn 微软 神谕 Salesforce的 树液 尤伯杯 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是数组的大小。