首页 > 试题广场 >

没有重复项数字的全排列

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

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

数据范围：数字个数 $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]]

算法知识视频讲解

Python 3

JianYue

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

发表于 2022-09-15 22:37:57 回复(0)

Python 3

正循环圈圈

深度优先遍历：

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)

Python 3

牛客808686245号

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

发表于 2022-08-25 22:33:10 回复(0)

Python 3

蓝鲸与风

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    res=[]
    def trace(self,path, nums):
        if len(path)==len(nums):
            self.res.append(path[:])#为什么path不行
            return 
        for num in nums:
            if num in path:
                continue
            path.append(num)
            self.trace(path, nums)
            #回溯
            path.pop()
            
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        num.sort()
        self.trace([],num)
        return self.res

发表于 2022-08-20 17:32:59 回复(0)

Python 3

牛客150225125号

递归+迭代器

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

发表于 2022-07-28 10:38:20 回复(0)

Python 3

咸鱼翻身哈哈哈

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

nums = list(itertools.permutations(num, len(num)))
nums = list(map(list, set(nums)))
return nums

发表于 2022-06-25 20:34:27 回复(0)

Python 3

牛客788327651号

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        n = len(num)
        if n == 1:
            return [num]
        res = []
        for i in range(n):
            except_i = self.permute(num[:i]+num[i+1:])
            for l in except_i:
                res.append([num[i]]+l)
        return res

发表于 2022-06-07 21:11:02 回复(0)

Python 3

时吾

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        results = []
        ln = len(num)
        def dfs(path=[]):
            if len(path) == ln:
                results.append(path)
                return

            for c in num:
                if c in path: continue
                dfs(path+[c])
        dfs()
        return results

发表于 2022-05-26 22:21:35 回复(0)

Python 3

宫城良田z

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        def dfs(cur, nums):
            if len(cur) == len(num):
                return cur
            for index, i in enumerate(nums):
                tmp = dfs(cur + [i], nums[ : index] + nums[index + 1 : ])
                if tmp: res.append(tmp)
            return # for循环结束, 返回None

        res = []
        num.sort()
        dfs([], num)

        return res

发表于 2022-04-30 10:28:06 回复(0)

Python 3

四片三明治

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        result=[]
        def trace(path,choices):
            if len(path)==len(num):
                result.append(list(path))
                return
            for item in choices:
                if item in path:
                    continue
                path.append(item)
                trace(path, choices)
                path.pop()
        trace([], num)
        return result

发表于 2022-04-12 19:59:14 回复(0)

Python 3

Joy_9

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        res=[]
        def backtrace(node,path):
            if len(path)==len(num):
                res.append(path)
                return
            for i in range(len(node)):
                cur_node=node[:i]+node[i+1:]
                cur_path=path+[node[i]]
                backtrace(cur_node, cur_path)
        backtrace(num, [])
        return res

发表于 2022-01-20 09:20:45 回复(0)

Python 3

牛客38477449号

class Solution:
    def permute(self , num ):
        # write code here
        if num == []:
            return []
        visited = [False] * len(num)
        res, path = [], []
        def dfs(visited, path, num):
            if len(path) == len(num):
                res.append(path[:])
                return
            for i in range(len(num)):
                if visited[i] == False:
                    visited[i] = True
                    path.append(num[i])
                    dfs(visited, path, num)
                    path.pop()
                    visited[i] = False
        for i in range(len(num)):
            visited[i] = True
            path.append(num[i])
            dfs(visited, path, num)
            path.pop()
            visited[i] = False
        return sorted(res)

发表于 2021-09-15 17:42:49 回复(0)

Python 3

yusei_ooo

class Solution:
    def permute(self , num ):
        # write code here
        num.sort()
        def dfs(res,path,depth,used):
            if depth == n:
                res.append(path[:])
            for i in range(n):
                if used[i] == 1:
                    continue
                used[i] = 1
                path.append(num[i])
                dfs(res,path,depth+1,used)
                path.pop()
                used[i] = 0
        res = []
        n = len(num)
        used = [0]*n
        dfs(res,[],0,used)
        return res

发表于 2021-08-16 22:05:07 回复(0)