剑指 Offer II 083 没有重复元素集合的全排列｜

发表于

这是我参与11月更文挑战的第6天，活动详情查看：2021最后一次更文挑战

非常感谢你阅读本文~
欢迎【👍点赞】【⭐收藏】【📝评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://juejin.cn/user/2771185768884824/posts 博客原创~

剑指 Offer II 083. 没有重复元素集合的全排列｜46. 全排列：

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

样例 1

1
2
3
4
5
ini复制代码输入：
	nums = [1,2,3]

输出：
	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

样例 2

1
2
3
4
5
lua复制代码输入：
	nums = [0,1]

输出：
	[[0,1],[1,0]]

样例 3

1
2
3
4
5
lua复制代码输入：
	nums = [1]
	
输出：
	[[1]]

提示

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

分析

  • 这道算法题采用递归，回溯法比较简单，谁要是非要用循环非递归，二当家的佩服。
  • 提示中说每个数字各不相同，那我们全排列就可以考虑成数字所在位置或者说是数组的下标的不同排列，因为数字都不同，所以我们就不必关心每个数字是几了。
  • 可以单开辟空间存储中间排列，这样我们需要能判断某个数字是否被选择过，可以用hash表存储当前排列结果，然后去看是否含有当前数字，但是这样似乎比较低效。
  • 每个位置的数字都不一样，所以我们直接存储一下某个位置的数字是否被使用即可。
  • 可以直接使用一个布尔数组存储访问过的位置，但是提示中说数字个数最多6个，那我们最多用6个二进制位就可以表示所有数字的已使用和未使用，一个 int 型变量足以，我们用这个 int 型变量的二进制位变化，去对应数字的已使用和未使用。
  • 也可以直接在原数组用交换的方式模拟排列，每个数字在所有位置上都排一次不就是全排列吗？先轮着放第一个位置，然后轮着放第二个位置，以此类推。

题解

java

不使用交换的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
java复制代码class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
            dfs(nums, new ArrayList<>(nums.length), 0, ans);
            return ans;
	}
	
	private void dfs(int[] nums, List<Integer> row, int flag, List<List<Integer>> ans) {
            if (row.size() == nums.length) {
                ans.add(new ArrayList<>(row));
                return;
            }
            for (int i = 0; i < nums.length; ++i) {
                if (((flag >> i) & 1) == 0) {
                    row.add(nums[i]);
                    dfs(nums, row, flag | (1 << i), ans);
                    row.remove(row.size() - 1);
                }
            }
	}
}

使用交换的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
java复制代码class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
            backtrack(nums, 0, ans);
            return ans;
	}

	private void backtrack(int[] nums, int cur, List<List<Integer>> ans) {
            if (cur == nums.length) {               
                ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
                return;
            }
            // 当前位置保持不变，接着排下一个
            backtrack(nums, cur + 1, ans);
            // 换后面的某一个到当前位置
            for (int i = cur + 1; i < nums.length; ++i) {
                swap(nums, cur, i);
                backtrack(nums, cur + 1, ans);
                swap(nums, cur, i);
            }
	}

	private void swap(int[] nums, int a, int b) {
            nums[a] ^= nums[b];
            nums[b] ^= nums[a];
            nums[a] ^= nums[b];
	}
}

c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
c复制代码/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    *returnSize = numsSize;
    for (int i = 2; i < numsSize; ++i) {
        *returnSize *= i;
    }

    int **ans = (int **) malloc(sizeof(int *) * (*returnSize));
    *returnColumnSizes = (int *) malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < *returnSize; ++i) {
        ans[i] = (int *) malloc(sizeof(int) * numsSize);
        (*returnColumnSizes)[i] = numsSize;
    }

    int ansSize = 0;

    backtrack(nums, numsSize, 0, ans, &ansSize);

    return ans;
}

void backtrack(int* nums, int numsSize, int cur, int **ans, int *ansSize) {
    if (cur == numsSize) {
        for (int i = 0; i < numsSize; ++i) {
            ans[*ansSize][i] = nums[i];
        }
        *ansSize += 1;
        return;
    }
    // 当前位置保持不变，接着排下一个
    backtrack(nums, numsSize, cur + 1, ans, ansSize);
    // 换后面的某一个到当前位置
    for (int i = cur + 1; i < numsSize; ++i) {
        swap(nums, cur, i);
        backtrack(nums, numsSize, cur + 1, ans, ansSize);
        swap(nums, cur, i);
    }
}

void swap(int* nums, int a, int b) {
    nums[a] ^= nums[b];
    nums[b] ^= nums[a];
    nums[a] ^= nums[b];
}

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
cpp复制代码class Solution {
private:
    void backtrack(vector<int> &nums, int cur, vector<vector<int>> &ans) {
        if (cur == nums.size()) {
            ans.push_back(nums);
            return;
        }
        // 当前位置保持不变，接着排下一个
        backtrack(nums, cur + 1, ans);
        // 换后面的某一个到当前位置
        for (int i = cur + 1; i < nums.size(); ++i) {
            swap(nums[cur], nums[i]);
            backtrack(nums, cur + 1, ans);
            swap(nums[cur], nums[i]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;

        backtrack(nums, 0, ans);

        return ans;
    }
};

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
python复制代码class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []

        def backtrack(cur: int) -> None:
            if cur == n:
                ans.append(nums[:])
                return
            # 当前位置保持不变，接着排下一个
            backtrack(cur + 1)
            # 换后面的某一个到当前位置
            for i in range(cur + 1, n):
                nums[cur], nums[i] = nums[i], nums[cur]
                backtrack(cur + 1)
                nums[cur], nums[i] = nums[i], nums[cur]

        backtrack(0)
        return ans

go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
go复制代码func permute(nums []int) [][]int {
    n := len(nums)
    var ans [][]int

    var backtrack func(cur int)
    backtrack = func(cur int) {
        if cur == n {
            ans = append(ans, append([]int{}, nums...))
            return
        }
        // 当前位置保持不变，接着排下一个
        backtrack(cur + 1)
        // 换后面的某一个到当前位置
        for i := cur + 1; i < n; i++ {
            nums[cur], nums[i] = nums[i], nums[cur]
            backtrack(cur + 1)
            nums[cur], nums[i] = nums[i], nums[cur]
        }
    }

    backtrack(0)

    return ans
}

rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
rust复制代码impl Solution {
    pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut ans = Vec::new();

        Solution::backtrack(&mut nums, 0, &mut ans);

        ans
    }

    fn backtrack(nums: &mut Vec<i32>, cur: usize, ans: &mut Vec<Vec<i32>>) {
        if cur == nums.len() {
            ans.push(nums.clone());
            return;
        }
        // 当前位置保持不变，接着排下一个
        Solution::backtrack(nums, cur + 1, ans);
        // 换后面的某一个到当前位置
        (cur + 1..nums.len()).for_each(|i| {
            nums.swap(cur, i);
            Solution::backtrack(nums, cur + 1, ans);
            nums.swap(cur, i);
        });
    }
}

在这里插入图片描述

原题传送门：https://leetcode-cn.com/problems/VvJkup/

原题传送门：https://leetcode-cn.com/problems/permutations/

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%