首页 > 试题广场 >

没有重复项数字的全排列

[编程题]没有重复项数字的全排列
  • 热度指数:73087 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一组数字,返回该组数字的所有排列
例如:
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
(以数字在数组中的位置靠前为优先级,按字典序排列输出。)

数据范围:数字个数
要求:空间复杂度 ,时间复杂度
示例1

输入

[1,2,3]

输出

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例2

输入

[1]

输出

[[1]]
// 解法二
    ArrayList<ArrayList<Integer>> res2 = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute2(int[] num) {
        permutation(num, 0);
        return res2;
    }

    public void permutation(int[] num, int start) {
        if(start == num.length - 1) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < num.length; i++) {
                list.add(num[i]);
            }
            res2.add(list);
        }

        for (int i = start; i < num.length; i++) {
            swap(num, i, start);
            permutation(num, start + 1);
            swap(num, i, start);
        }

    }

    public void swap(int[] num, int i, int j) {
        int temp;
        temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
编辑于 2018-03-20 11:02:36 回复(1)
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
        permutation(res,num,0);
        return res;
    }
    void permutation(vector<vector<int> > &res,vector<int> &num,int s)
    {
    	if(s == num.size()-1)
    		res.push_back(num);
    	else{
    		for(int i=s;i<num.size();i++)
    		{
    			swap(num[s],num[i]);
				permutation(res,num,s+1);
				swap(num[s],num[i]);
			}
		}    		
	}
};

发表于 2017-08-13 06:35:56 回复(7)
/**
 * 46. Permutations
 * @author Jacob
 * 题意:求数组的全排列
 */
public class Demo1 {
	ArrayList<ArrayList<Integer>> res;

	public ArrayList<ArrayList<Integer>> permute(int[] nums) {
		res = new ArrayList<ArrayList<Integer>>();
		if (nums == null || nums.length < 1)
			return res;
		//对数组元素进行从小到大排序
		Arrays.sort(nums);
		ArrayList<Integer> list = new ArrayList<Integer>();

		solve(list, nums);

		return res;
	}

	private void solve(ArrayList<Integer> list, int[] nums) {
		if (list.size() == nums.length) {
			res.add(new ArrayList<Integer>(list));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if (!list.contains(nums[i])) {
				list.add(nums[i]);
				solve(list, nums);
				list.remove(list.size() - 1);
			}
		}
	}
}

发表于 2017-08-19 10:32:00 回复(11)
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # 递归结束条件
        if len(num) <= 1:
            return [num]
        ret = []
        for i, e in enumerate(num):
            r = self.permute(num[:i] + num[i+1:])
            ret += [[e] + k for k in r]
        return ret

发表于 2023-03-02 11:44:56 回复(2)
是不是应该改下结果判断,如果明确需要结果字典序排列,请在题目处注明,要不就把结果集改成set:
不通过
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为12.50%

用例:
[1,2,3]

对应输出应该为:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

你的输出为:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]


发表于 2019-11-07 10:15:34 回复(2)
排列的时候每次都需要从数组第一个元素开始,所以只需要used数组判断是否使用过,不需要每次递归用start刷新位置。
import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> ls = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        int[] used = new int[num.length];
        dfs(num,used);
        return res;
    }
    private void dfs(int[] a,int[] used) {
        if(ls.size() == a.length) {
            res.add(new ArrayList<>(ls));
            return;
        }
        for(int i = 0; i < a.length; i++) {
            if(used[i] == 1) continue;
            used[i] = 1;
            ls.add(a[i]);
            dfs(a,used);
            used[i] = 0;
            ls.remove(ls.size()-1);
        }
    }
}


发表于 2021-06-17 11:01:58 回复(0)

做烂了的回溯

class Solution {
public:
    void dfs(int cur, vector<int> &tmp, vector<int> &taken, vector<int> &num, 
             vector<vector<int> > &res){
        int n = num.size();
        if(tmp.size() == n){res.push_back(tmp);return;}
        for(int i = 0; i < n; i++){
            if(!taken[i]){
                taken[i] = 1;
                tmp.push_back(num[i]);
                dfs(i+1, tmp, taken, num, res);
                tmp.pop_back();
                taken[i] = 0;
            }
        }
    }

    vector<vector<int> > permute(vector<int> &num) {
        vector<int> tmp; 
        vector<int> taken(num.size(), 0);
        vector<vector<int> > res;
        dfs(0, tmp, taken, num, res);
        return res;
    }
};
发表于 2019-07-05 21:05:48 回复(0)

递归 + 回溯 不回溯的话num还停留在上一次递归排列的状态,可能会导致出现漏排的情况
时间复杂度:O(n!) 空间复杂度:O(n) 递归栈的深度
还有注意添加排列好的num时使用深拷贝

import copy
class Solution:
    def recursion(self, num, res, index):
        if index == len(num) - 1:
            res.append(copy.deepcopy(num))
        else:
            for i in range(index, len(num)):
                temp = num[i]
                num[i] = num[index]
                num[index] = temp
                self.recursion(num, res, index+1)
                temp = num[i]
                num[i] = num[index]
                num[index] = temp

    def permute(self , num: List[int]) -> List[List[int]]:
        num.sort()
        res = []
        self.recursion(num, res, 0)
        return res
发表于 2022-05-19 17:35:51 回复(1)
import java.util.*;
## 经典回溯
public class Solution {
    List<Integer> list = new ArrayList<>();
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        Arrays.sort(num);
        dfs(num,list);
        return result;
    }

    private void dfs(int[] num,List<Integer> list){
        if(list.size() == num.length){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < num.length; i ++){
            if(list.contains(num[i])){
                continue;
            }
            list.add(num[i]);
            dfs(num,list);

            list.remove(list.size() - 1);
        }

    }
}

发表于 2023-02-27 17:40:04 回复(1)
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        // 时间复杂度O(N!),空间复杂度O(N!)
        vector<vector<int>> res;
        vector<int> path;
        sort(num.begin(), num.end());
        recursion(num, path, res);
        return res;
    }
    void recursion(vector<int> &num, vector<int> &path, vector<vector<int>> &res) {
        if (num.empty()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < num.size(); ++i) {
            path.push_back(num[i]);
            vector<int> tmp(num);  // 拷贝一份,删除path中加入的num[i]
            tmp.erase(tmp.begin() + i);
            recursion(tmp, path, res);
            path.pop_back();
        }
    }
};

发表于 2022-10-14 21:29:19 回复(0)

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
void dfs(int* num, int index, int numLen, int* returnSize, int** returnColumnSizes, int **ret)
{
    int j = 0;
    if (index == numLen) {
        ret[*returnSize] = (int *)malloc(numLen * sizeof(int));
        for (j = 0; j < numLen; j++) {
           ret[*returnSize][j]  = num[j];
        }
        (*returnColumnSizes)[*returnSize] = numLen;
        (*returnSize)++;
        return;
    }
    
    for (j = index; j < numLen; j++) {
        swap(&num[j], &num[index]);
        dfs(num, index+1, numLen, returnSize,  returnColumnSizes, ret);
        swap(&num[j], &num[index]);
    }
    return;
}
int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    // write code here
    *returnColumnSizes = (int*)malloc(sizeof(int) * 100001);
    int **ret = (int**)malloc(sizeof(int*) * 100001);
    *returnSize = 0;
    dfs(num, 0, numLen, returnSize,  returnColumnSizes, ret);
   
    return ret;
}
发表于 2022-05-15 10:41:46 回复(3)
class Solution {
public:
    void pushVec(vector<int> num, int index){
        per.push_back(num);
        for(int i = index; i < num.size()-1; ++ i){
            for(int j = i+1; j < num.size(); ++ j){
                swap(num[i],num[j]);
                pushVec(num,i+1);
                swap(num[i],num[j]);
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        pushVec(num,0);
        return per;
    }
private:
    vector<vector<int> > per;
};

发表于 2018-02-14 20:16:46 回复(0)
class Solution {
public:
void dfs(vector<int> &num,vector<vector<int>> &res,int begin)
{
    if(begin == num.size())
        res.push_back(num);
    for(int i=begin;i<num.size();i++)
    {
        swap(num[i],num[begin]);
        dfs(num,res,begin+1);
        swap(num[i],num[begin]);
    }
}
vector<vector<int> > permute(vector<int> &num)
{
        vector<vector<int>> res;
        if(num.size()==0)
            return res;
        sort(num.begin(),num.end());
        dfs(num,res,0);
        return res;
}
};

发表于 2017-07-14 15:28:33 回复(0)
class Solution {
public:
    //next_permutation:会取得[first,last)所标识之序列的下一个排列组合
    //如果没有下一个排列组合,便返回false,否则返回true。
   vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
	sort(num.begin(), num.end());
	do 
	{
		res.push_back(num);
	} while (next_permutation(num.begin(),num.end()));
	return res;
    }
};

编辑于 2016-09-02 18:12:47 回复(2)
全排列生成么,因为没说输入时字典序,所以不能用next_permutation
所以得自己写全排列
递归,交换i和开头,

class Solution {
    void permutation(vector<vector<int> >&ans,vector<int>& num,int l)
    {
        if(l == num.size()-1)
            ans.push_back(num);
        else
        {
            for(int i=l;i<num.size();i++)
            {
                swap(num[l],num[i]);
                permutation(ans,num,l+1);
                swap(num[l],num[i]);
            }
        }
    }
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > ans;
        permutation(ans,num,0);
        return ans;
    }
};


发表于 2016-09-02 17:18:36 回复(3)
public ArrayList<ArrayList<Integer>> permute (int[] num) {
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        ArrayList<Integer> list=new ArrayList<>();
        build(num,ans,list);
        return ans;
    }
    public void build(int[] num,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list){
        if(list.size()==num.length){  //截至条件(终止条件)
            ans.add(new ArrayList<>(list));
        }
        for(int i=0;i<num.length;i++){
            if(list.contains(num[i])){    //因为这个题没有重复的数字,   所以当list中已经有了这个数字,那就剪枝
                continue;
            }
            list.add(num[i]);
            build(num,ans,list);
            list.remove(list.size()-1);
        }
    }

发表于 2023-07-14 15:46:42 回复(2)
递归回溯版本
为什么要发这个呢,看前面的题解,是用交换位置来解决排序问题,说实话我真想不到这种思路
对于这个问题我思维第一反应,就是把子问题看作是n大小的序列排列问题
这样逐步分解到大小为1的vector,这样做的好处就是契合题目要求,最终结果就是按字典排序输出的。
而交换位置的话,是需要另外sort一下的,当然你不sort也能通过,结果不会检查字典顺序
以下是我照此思路递归实现的
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> res;
        vector<int> ans;

        recursion(num, ans, res);
        return res;
    }

    void recursion(vector<int> vec, vector<int> &ans, vector<vector<int>> &res){
        if(vec.size()==1){
            ans.push_back(vec[0]);
            res.push_back(ans);
            ans.pop_back();
            return;
        }

        for(int i : vec){
            ans.push_back(i);
            vector<int> newvec;
            for (int j : vec){
                if(i!=j) newvec.push_back(j);
            }
            recursion(newvec, ans, res);
            ans.pop_back();
        }
    }
};



发表于 2023-03-18 23:48:58 回复(0)
深度优先遍历:
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        n = len(num)
        res_all = []   # all result
        res = []   # result
        
        def dfs(res):  # dfs函数是permute函数的闭包函数
            if len(res) == n:
                res_all.append(res[:])  # res[:]可以开辟新内存存储结果,防止被下面的res.pop()影响
            for i in range(n):
                if num[i] not in res:
                    res.append(num[i])
                    dfs(res)
                    res.pop()
        dfs(res)
        
        return res_all


发表于 2022-09-08 20:24:42 回复(0)
public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    int len;
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        if(num==null||num.length==0) return ans;
        //先对数组排序保证最后返回的结果是按字典排序输出
        Arrays.sort(num);
        len = num.length;
        //创建一个数组记录已经加入数组的元素
        boolean[] isVisi = new boolean[len];
        //递归添加元素
        dfs(num,isVisi,new ArrayList());
        return ans;
    }
    void dfs(int[] num,boolean[] vis,ArrayList<Integer> ls){
        if(ls.size()==len){
            ans.add(new ArrayList(ls));
            return;
        }
        for(int i = 0;i<len;i++){
            if(vis[i]) continue;
            vis[i] = true;
            ls.add(num[i]);
            dfs(num,vis,ls);
            //回溯
            vis[i] = false;
            ls.remove(ls.size()-1);
        }
    }
}

发表于 2022-07-16 11:26:21 回复(0)
class Solution {
public:
    vector<vector<int>>res;
    vector<vector<int> > permute(vector<int> &num) {
        sort(num.begin(),num.end());
        vector<int>track;
        backtrack(num,track);
        return res;
    }
    void backtrack(vector<int>&num,vector<int>&track){
        if(track.size()==num.size()){
            res.push_back(track);
            return;
        }
        for(int i=0;i<num.size();++i){
            if(count(track.begin(),track.end(),num[i])){
                continue;
            }
            track.push_back(num[i]);
            backtrack(num,track);
            track.pop_back();
        }
    }
};

发表于 2022-04-25 21:16:47 回复(0)