您现在的位置是:首页 >技术杂谈 >算法leetcode|47. 全排列 II(rust重拳出击)网站首页技术杂谈
算法leetcode|47. 全排列 II(rust重拳出击)
简介算法leetcode|47. 全排列 II(rust重拳出击)
47. 全排列 II:
给定一个可包含重复数字的序列 nums
,按任意顺序 返回所有不重复的全排列。
样例 1:
输入:
nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
样例 2:
输入:
nums = [1,2,3]
输出:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示:
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
分析:
- 面对这道算法题目,二当家的陷入了沉思。
- 要做全排列,回溯是大方向。
- 有重复的数字,又要不重复的排列,去重是必须的了。
- 要求是对排列去重,但是也可以理解为回溯时,跳过已经“尝试”过的数字。
- 如果数字很多,可以考虑计数排序法,这里顺序不重要,重要的是快速去重。
- 但是提示里说数字最多8个,那直接排序,同样顺序不重要,只是为了相同的数字挨在一起,每次回溯跳过相同数字即可。
题解:
rust
impl Solution {
pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
fn backtrack(nums: &Vec<i32>, ans: &mut Vec<Vec<i32>>, vis: &mut Vec<bool>, row: &mut Vec<i32>) {
if row.len() == nums.len() {
ans.push(row.clone());
return;
}
nums.iter().enumerate().for_each(|(i, v)| {
if !vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1]) {
row.push(nums[i]);
vis[i] = true;
backtrack(nums, ans, vis, row);
row.pop();
vis[i] = false;
}
});
}
let mut ans = Vec::new();
nums.sort();
let mut vis = vec![false; nums.len()];
let mut row = Vec::new();
backtrack(&mut nums, &mut ans, &mut vis, &mut row);
return ans;
}
}
go
func permuteUnique(nums []int) (ans [][]int) {
var backtrack func([]bool, []int)
backtrack = func(vis []bool, row []int) {
if len(row) == len(nums) {
ans = append(ans, append([]int(nil), row...))
return
}
for i, v := range nums {
if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
continue
}
row = append(row, v)
vis[i] = true
backtrack(vis, row)
row = row[:len(row)-1]
vis[i] = false
}
}
sort.Ints(nums)
backtrack(make([]bool, len(nums)), []int{})
return
}
c++
class Solution {
private:
void backtrack(vector<int>& nums, vector<vector<int>>& ans, vector<bool>& vis, vector<int>& row) {
if (row.size() == nums.size()) {
ans.emplace_back(row);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
continue;
}
row.emplace_back(nums[i]);
vis[i] = true;
backtrack(nums, ans, vis, row);
row.pop_back();
vis[i] = false;
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> row;
vector<bool> vis(nums.size(), false);
sort(nums.begin(), nums.end());
backtrack(nums, ans, vis, row);
return ans;
}
};
c
int cmp(void* a, void* b) {
return *(int*)a - *(int*)b;
}
void backtrack(int* nums, int numSize, int** ans, int* ansSize, bool* vis, int* row, int idx) {
if (idx == numSize) {
int *tmp = malloc(sizeof(int) * numSize);
memcpy(tmp, row, sizeof(int) * numSize);
ans[(*ansSize)++] = tmp;
return;
}
for (int i = 0; i < numSize; ++i) {
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
continue;
}
row[idx] = nums[i];
vis[i] = true;
backtrack(nums, numSize, ans, ansSize, vis, row, idx + 1);
vis[i] = false;
}
}
/**
* 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** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
int** ans = malloc(sizeof(int*) * 2001);
int* row = malloc(sizeof(int) * numsSize);
bool* vis = malloc(sizeof(bool) * numsSize);
memset(vis, false, sizeof(bool) * numsSize);
qsort(nums, numsSize, sizeof(int), cmp);
*returnSize = 0;
backtrack(nums, numsSize, ans, returnSize, vis, row, 0);
*returnColumnSizes = malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < *returnSize; i++) {
(*returnColumnSizes)[i] = numsSize;
}
return ans;
}
python
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(nums: List[int], ans: List[List[int]], vis: List[bool], row: List[int]):
if len(row) == len(nums):
ans.append(row.copy())
return
for i in range(len(nums)):
if not vis[i]:
if i > 0 and nums[i] == nums[i - 1] and not vis[i - 1]:
continue
row.append(nums[i])
vis[i] = True
backtrack(nums, ans, vis, row)
row.pop()
vis[i] = False
nums.sort()
ans = []
backtrack(nums, ans, [False] * len(nums), [])
return ans
java
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
backtrack(nums, ans, new boolean[nums.length], new LinkedList<>());
return ans;
}
private void backtrack(int[] nums, List<List<Integer>> ans, boolean[] vis, Deque<Integer> row) {
if (row.size() == nums.length) {
ans.add(new ArrayList<>(row));
return;
}
for (int i = 0; i < nums.length; ++i) {
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
continue;
}
row.push(nums[i]);
vis[i] = true;
backtrack(nums, ans, vis, row);
row.pop();
vis[i] = false;
}
}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。