首页 > 试题广场 >

没有重复项数字的全排列

[编程题]没有重复项数字的全排列
  • 热度指数：75509 时间限制：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]]
算法知识视频讲解
添加回答
Java
牛客839384289号头像 牛客839384289号 
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();

public ArrayList<ArrayList<Integer>> permute (int[] num) {
    // write code here
    Arrays.sort(num);
    recur(num ,new boolean[num.length] ,new ArrayList<>());
    return res;
}

public void recur(int[] num ,boolean[] flag ,ArrayList<Integer> list){
    if(list.size()==num.length){
        res.add(new ArrayList<>(list));
        return;
    }
    for(int i=0;i<num.length;i++){
        if((i>0 && num[i]==num[i-1] && !flag[i]) || flag[i]){
            continue;
        }
        list.add(num[i]);
        flag[i]=true;
        recur(num ,flag ,list);
        flag[i]=false;
        list.remove(list.size()-1);
    }
}

编辑于 2024-03-10 13:21:22 回复(0)
Java
-Panda君-头像 -Panda君-
从上图可以看出，当只有到遍历到叶子节点才会得到一个排列结果，因此递归出口是是使用完所有的数字，也就是这个存放排列组合的栈的大小等于数组的长度； 
        if(num.length == list.size()){
            res.add(new ArrayList<>(list));
            return;
        }
递归回溯套路
1.选择
2.递归/回溯
3.撤销选择 
public class Solution {
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        boolean[] visit = new boolean[num.length];
        dfs(num,res,list,visit);
        return res;
    }

    private void dfs(int[] num, ArrayList<ArrayList<Integer>> res, LinkedList<Integer>  list, boolean[] visit) {
        if(num.length == list.size()){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=0;i<num.length;i++){
            if(visit[i]){
                continue;
            }
            visit[i] = true;
            list.add(num[i]);
            dfs(num,res,list,visit);
            list.pollLast();
            visit[i] = false;
        }
    }
}



编辑于 2024-01-29 17:23:25 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
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)
Java
MorpheusNeo头像 MorpheusNeo 
import java.util.*;

import java.util.stream.Collectors;

public class Solution {

    private ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> current = new ArrayList<Integer>();

    public ArrayList<ArrayList<Integer>> permute(int[] num) {

        int max = getMax(num);
        int[] numCount = new int[max + 1];
        for (int idx = 0; idx < num.length; idx++) {
            numCount[num[idx]]++;
        }
        dfs(num, numCount, num.length);
        Set<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(this.all);
        this.all.clear();
        this.all.addAll(set);
        Collections.sort(this.all, new Comparator<ArrayList<Integer>>() {
            public int compare(ArrayList<Integer> self, ArrayList<Integer> other) {
                int min = Math.min(self.size(), other.size());
                for (int idx = 0; idx < min; idx++) {
                    if (self.get(idx) != other.get(idx)) {
                        return self.get(idx).compareTo(other.get(idx));
                    }
                }
                if (self.size() > other.size()) {
                    return self.get(min + 1);
                } else if (self.size() < other.size()) {
                    return other.get(min + 1);
                }
                return 0;
            }
        });
        return this.all;
    }

    public void dfs(int[] num, int[] numCount, int n) {
        if (this.current.size() == n) {
            this.all.add((ArrayList<Integer>)this.current.clone());
            return;
        }
        for (int idx = 0; idx < n; idx++) {
            int count = getCount(this.current, num[idx]);
            if (count < numCount[num[idx]]) {
                this.current.add(num[idx]);
                dfs(num, numCount, n);
                this.current.remove(this.current.size() - 1);
            }
        }
    }

    public static int getCount(ArrayList<Integer> list, int num) {
        long count = list.stream().filter(item->item == num).collect(
                         Collectors.counting());
        return Long.valueOf(count).intValue();
    }

    public static int getMax(int[] num) {
        int max = Integer.MIN_VALUE;
        for (int idx = 0; idx < num.length; idx++) {
            if (max < num[idx]) {
                max = num[idx];
            }
        }
        return max;
    }
}

发表于 2023-05-07 22:23:42 回复(0)
Java
嗯好248216头像 嗯好248216
import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        LinkedList<Integer> indexList = new LinkedList<>();
        def(result, temp, num, indexList);
        return result;
    }

    public void def(ArrayList<ArrayList<Integer>> result, LinkedList<Integer> temp,
                    int[] num, LinkedList<Integer> indexList) {
            if (indexList.size() == num.length) {
                System.out.println(temp);
                result.add(new ArrayList<>(temp));
                return;
            }
            for(int i = 0; i < num.length; i++) {
                if (indexList.contains(i)) {
                    continue;
                }
                temp.add(num[i]);
                indexList.add(i);
                def(result, temp, num, indexList);
                indexList.removeLast();
                temp.removeLast();
            }
    }
}
发表于 2023-04-03 11:17:59 回复(0)
Java
听风起云头像 听风起云 
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)
Java
羽落星辰头像 羽落星辰
力扣第46题 
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        test(lists,new ArrayList<>(),num);
        return lists;
    }

    public static void test(ArrayList<ArrayList<Integer>> lists, ArrayList<Integer> list, int[] nums) {
        if (list.size() == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i=0;i<nums.length;i++) {
            if (list.contains(nums[i])) continue;
            list.add(nums[i]);
            test(lists,list,nums);
            list.remove(list.size()-1);
        }
    }


发表于 2022-12-03 19:59:45 回复(0)
Java
牛客嗷嗷头像 牛客嗷嗷 
import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> list = new ArrayList<>();
        backTrack(num, list);
        return res;
    }

    public  void backTrack(int[] num, ArrayList<Integer> list) {
        if (list.size() == num.length) {
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < num.length; i++) {
            if (list.contains(num[i]))
                continue;

            list.add(num[i]);
            backTrack(num, list);
            list.remove(list.size() - 1);
        }
    }
}

发表于 2022-09-28 17:58:00 回复(1)
Java
牛客用户007头像 牛客用户007
知道思路就很简单了 
import java.util.*;

public class Solution {

    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        boolean[] isUsed = new boolean[num.length];
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(num);

        dfs(num, isUsed, list);

        return res;
    }

    public void dfs(int[] num, boolean[] isUsed, ArrayList<Integer> list) {
        if (list.size() == num.length) {
            res.add(new ArrayList(list));
        }

        for (int i = 0; i < num.length; i ++) {
            if (isUsed[i] == true) continue;
            if (i > 1 && num[i] == num[i - 1]) continue;
            list.add(num[i]);
            isUsed[i] = true;
            dfs(num, isUsed, list);
            isUsed[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

发表于 2022-08-09 14:24:42 回复(1)
Java
yxjing头像 yxjing 
import java.util.*;

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

发表于 2022-08-03 16:13:12 回复(0)
Java
lizi-hust头像 lizi-hust 
import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> track = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        backtrack(num);
        return res;
    }
    
    public void backtrack(int[] num){
        if(track.size()==num.length) {
            res.add(new ArrayList<Integer>(track));
            return;
        }
        
        for(int i : num){
            if(track.contains(i)) continue;
            track.add(i);
            backtrack(num);
            track.remove(track.size()-1);
        }
        return;
    }
}

发表于 2022-07-19 16:06:42 回复(0)
Java
wjp-niuke头像 wjp-niuke
import java.util.*;

public class Solution {
 LinkedList<LinkedList> list =
            new LinkedList<LinkedList>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
   
        LinkedList<Integer> innerlist = new LinkedList<>();
        
        track(num,innerlist);

// LinkedList 转为ArrayList
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            ArrayList<Integer> ilist = new ArrayList<>();
            for (int j = 0; j < list.get(i).size(); j++) {
                ilist.add((Integer)list.get(i).get(j));
            }
            arrayLists.add(ilist);


        }

        return  arrayLists;

    }
    public void track(int [] num, LinkedList<Integer> inlist){
        if (inlist.size()==num.length) {
//这个地方要new
            list.add( new LinkedList(inlist));
            return;
        }

        for (int i = 0; i < num.length; i++) {
            if (inlist.contains(num[i])) {
                continue;
            }
            inlist.add(num[i]);
            track(num,inlist);
            inlist.removeLast();
        }
    }
}
发表于 2022-07-17 12:17:05 回复(0)
Java
Bug专家头像 Bug专家 
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)
Java
小样yx头像 小样yx 
import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        Arrays.sort(num); 
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(num.length == 0){
            return res;
        }
        ArrayList<Integer> list = new ArrayList<>();
        //数组转list集合（重点！！！）
        for(int n : num){
            list.add(n);
        }
        recursion(res, list, 0);
        return res;
    }
    
    int temp = 0;
    public void swap(ArrayList<Integer> list, int i1, int i2){
        temp = list.get(i1);
        list.set(i1, list.get(i2));
        list.set(i2, temp);
    }
    
    public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list, int index){
        if(index == list.size() - 1){
            res.add(new ArrayList<>(list));//官方答案这里写错了，不new的话，存的内存地址就是同一个，那么就会相同结果
        }else{
            for(int i = index; i < list.size(); i++){
                swap(list, i, index);//递归
                recursion(res, list, index + 1);
                swap(list, i, index);//回溯
            }
        }
    }
}


发表于 2022-06-16 22:14:52 回复(0)
Java
牛客148901号头像 牛客148901号 
import java.util.*;

public class Solution {
    public void swap(ArrayList<Integer> nums, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }

    public void recursive(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> nums, int startIndex) {
        if (startIndex == nums.size() - 1) {
            result.add(new ArrayList<>(nums));
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            swap(nums, startIndex, i);
            recursive(result, nums, startIndex + 1);
            swap(nums, startIndex, i);
        }
    }

    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> nums = new ArrayList<>();
        for (int n : num) {
            nums.add(n);
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        recursive(result, nums, 0);
        return result;
    }
}

发表于 2022-06-03 22:20:30 回复(0)
Java
牛客571536534号头像 牛客571536534号 
import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        int len = num.length;
        Deque path = new ArrayDeque();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[len];
        if (len == 0){
            return res;
        }

        dfs(path,used,num,res,0,len);
        return res;
        
    }
    
    public static void dfs(Deque<Integer> path, boolean[] used, int[] nums, ArrayList<ArrayList<Integer>> res,int depth,int len){
        if (depth == len){
            //终止递归
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]){
                path.addLast(nums[i]);
                used[i] = true;
                dfs(path,used,nums,res,depth + 1,len);
                used[i] = false;
                path.removeLast();
            }
        }
    }
}

发表于 2022-05-06 14:43:36 回复(0)
Java
阿biao头像 阿biao 
public class Solution {
    
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        help(num);
        return res;
    }
    
    public void help(int[] num){
        if(list.size() == num.length){
            res.add(new ArrayList(list));
            return; 
        }
        
        for(int i = 0; i < num.length;i++){
            if(list.contains(num[i])) continue;
            list.add(num[i]);
            help(num);
            list.remove(list.size()-1);
        }
    }
}

发表于 2022-04-09 21:02:48 回复(0)
Java
我是小韩头像 我是小韩

简单粗暴：DFS + 回溯

import java.util.*;

public class Solution {
        // 返回结果
 private static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
 public ArrayList<ArrayList<Integer>> permute(int[] num) {
        boolean[] flags = new boolean[num.length];
        dfs(num, flags, new LinkedList<>());
        return result;
    }

    private void dfs(int[] num, boolean[] flags, LinkedList<Integer> temp) {
        // 结束标志
        if (temp.size() == num.length) {
            result.add(new ArrayList<>(temp));
            return;
        }

        for (int i = 0; i < num.length; i++) {
            if (flags[i]) {
                continue;
            }
            // 前进
            flags[i] = true;
            temp.add(num[i]);
            dfs(num, flags, temp);
            // 回退
            flags[i] = false;
            temp.removeLast();
        }

    }
}
发表于 2022-04-08 00:01:27 回复(0)
Java
可有可无q头像 可有可无q 
import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    // 记录访问过的数字
    boolean[] vis;
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> tempRes = new ArrayList<>();
        vis = new boolean[num.length];
        for(int i = 0;i<vis.length;i++)
            vis[i] = false;
        backTrace(num,tempRes);
        return res;
    }
    public void backTrace(int[] num,ArrayList<Integer> temp){
        if(temp.size() == num.length){
            res.add(new ArrayList(temp));
            return;
        }
        for(int i = 0;i<num.length;i++){
            if(vis[i])
                continue;
            temp.add(num[i]);
            vis[i] = true;
            backTrace(num,temp);
            // 回退
            temp.remove(temp.size()-1);
            vis[i] = false;
        }
    }
}

发表于 2022-03-19 10:23:18 回复(0)
提交观点

问题信息

递归
难度：
42条回答 25120浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号