首页 > 试题广场 >

没有重复项数字的全排列

[编程题]没有重复项数字的全排列

热度指数：74582 时间限制：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].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 $0 < n \le 6$

要求：空间复杂度 $O(n!)$ ，时间复杂度 $O(n!）$

示例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]]

算法知识视频讲解

查看答案及解析

Python3

计算机里打灰的

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        if len(num)==1:
            return [num]
        u=[]
        for i in range(len(num)):
            j=num[:i]+num[i+1:]
            k=self.permute(j)
            for j in k:
                u.append([num[i]]+j)
            
        return u

编辑于 2024-03-25 21:19:32 回复(0)

Python3

牛客782212540号

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        num_len = len(num)
        if num_len == 0:
            return []
        elif num_len == 1:
            return [num]
        elif num_len == 2:
            return [[num[0],num[1]],[num[1],num[0]]]
        res = []
        for i in range(num_len):
            extra_arr = [num[x] for x in range(num_len) if x != i]
            res.extend([[num[i]]+p for p in self.permute(extra_arr)])
        return res

编辑于 2024-03-24 18:40:11 回复(0)

Python3

川流不息憨憨

from itertools import permutations
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        return list(permutations(num, len(num)))

编辑于 2024-03-19 21:40:37 回复(0)

Python3

Ganmanea

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        if (len(num)) < 2:
            return [num]
        if len(num) == 2:
            return [[num[0], num[1]], [num[1], num[0]]]
        output = []
        for i in range(len(num)):
            new_num = num[:i] + num[i+1:]
            cur = self.permute(new_num)
            for j in cur:
                output.append([num[i]] + j)
        return output

递归到元素为 2 的情况就可以了。

发表于 2023-12-30 11:29:36 回复(0)

Python3

对角线1

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        res = []
        n = len(num)
        if n <=1 :return [num]
        for i in range(n):
            for item in self.permute(num[:i]+num[i+1:]):
                temp = [num[i]]+item
                res.append(temp)
        return res

发表于 2023-11-13 11:17:23 回复(0)

Python3

momo牛牛

递归！

class Solution:

def permute(self , num: List[int]) -> List[List[int]]:

# write code here

if len(num) == 1:

return [num]

res = []

for i, n in enumerate(num):

res = res + [[n] + p for p in self.permute(num[i+1:] + num[:i])]

return res

发表于 2023-08-03 23:49:21 回复(0)

Python3

金黄多耀眼

python3，递归+回溯的直观思路

递归子问题：依次遍历num中的值，如果不在当前排列cur中则加入

终止条件：len(cur) == len(num)

回溯：cur中加入的元素，需要在调用子递归后弹出，以便后续情况的遍历

注意：将满足条件的cur加入结果列表res中时必须加上.copy()，否则res的结果全是空列表

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        if len(num) == 0 :
            return []
        if len(num) == 1:
            return [num]
        res = []
        cur = []

        def backtrack(num):
            if len(cur) == len(num):
                tmp = cur.copy() #必须copy，否则tmp的值为最终递归完毕后cur的值：[]
                res.append(tmp)
                print(cur)
                return
            for i in range(len(num)):
                if num[i] in cur:
                    continue
                cur.append(num[i])
                backtrack(num)
                cur.pop(-1)

        backtrack(num)
        print(res)
        return res

发表于 2023-04-18 12:17:30 回复(0)

Python3

Namely

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)

Python3

牛客670572580号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        ans=[] #存放全部结果的数组
        lens=len(num)
        cur = [0 for i in range(lens)] #存放全排列的数组‘】
        #permutation函数的意思是将num里面的数据进行全排列
        #排列的结果放在同样长度的cur表里面
        #当前函数执行的意思是，从nums数组里面选择一个数字放入cur[pos]里面
        def permutaltion (pos,lens,num,cur):
            if (pos==lens):
                ans.append([i for i in cur])  #排列结束，到达边界，加入结果数组
                return 
            for i in range(lens):  #尝试将num[i]放入cur[pos]中
                flag=0             #标记位
                for j in range(pos):#如果在nums[i]已经存在于cur[0..pos-1]中，则置1
                    if cur[j]==num[i]:   #因为一个数字在cur数组中只允许出现一次
                        flag=1    #如果已经出现，那么就要继续遍历nums数组找到合适的数字
                if flag==0:       #没有置1，证明nums[i]还未出现，可以选择
                    cur[pos]=num[i] #将nums[i]放入cur[pos]中
                    permutaltion(pos+1,lens,num,cur) #cur[0..pos]都已经安排好，所以下一次迭代需要为cur[pos+1]找到合适的数字
        permutaltion(0,lens,num,cur) 
        return ans

发表于 2022-12-26 23:45:59 回复(1)

Python3

新人帅哥

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        ans, path = [], []
        def dfs(num, vis):
            if len(path) == len(num):
                ans.append(path[:])
                return
            for i in range(len(num)):
                if not vis[i]:
                    path.append(num[i])
                    vis[i] = True
                    dfs(num, vis)
                    vis[i] = False
                    path.pop()
        vis = [False] * len(num)
        dfs(num, vis)
        return ans

发表于 2022-11-12 16:49:45 回复(0)

Python3

进步摩卡

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        n = len(num)
        def messsort(res:list[list[int]],arr:list,index:int):
            if index == len(arr) - 1:
                list2 = [ ]
                for i in arr:
                    list2.append(i)
                res.append(list2)

            else:
                for i in range(index,len(arr)):
                    cur = arr[index]
                    arr[index] = arr[i]
                    arr[i] = cur
                    messsort(res,arr,index + 1)
                    cur = arr[index]
                    arr[index] = arr[i]
                    arr[i] = cur
            return
        res = [ ]
        messsort(res,num,0)
        res.sort()
        return res

在写的时候遇到过append到列表里的东西居然被改写了，查了半天发现是往列表里append了一个指针。最后把需要append的东西重写了一边放进列表才解决问题。

发表于 2022-10-16 01:01:57 回复(0)

Python3

被加薪的突尼斯海怪很伤心

import copy
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here

        s=[]
        def a(num,layer):
            nonlocal s
            if layer == len(num):
                s.append(num)
            else:
                for j in range(layer, len(num)):
                    temp = num[layer]
                    num[layer] = num[j]
                    num[j] = temp
                    a(copy.deepcopy(num),layer+1)
        a(num,0)
        return s

发表于 2022-09-22 19:34:03 回复(0)

Python3

Vivimore

递归 + 回溯不回溯的话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)

Python3

瑾Biu

写了个递归

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num int整型一维数组
# @return int整型二维数组
#
class Solution:
def permute(self , num: List[int]) -> List[List[int]]:
# write code here
def arrange(num):
res = []
if len(num)<= 1:
return [num]
for i in range(len(num)):
for each in arrange(num[:i]+num[i+1:]):
each.insert(0,num[i])
res.append(each)

return res

return arrange(num)

发表于 2022-03-27 14:58:52 回复(1)