golang 数据结构 后端 算法leetcode｜47. 全排列 II（rust重拳出击）

文章目录

47. 全排列 II：样例 1：样例 2：提示：

分析：题解：rustgoc++cpythonjava

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) -> Vec> {

fn backtrack(nums: &Vec, ans: &mut Vec>, vis: &mut Vec, row: &mut Vec) {

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& nums, vector>& ans, vector& vis, vector& 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> permuteUnique(vector& nums) {

vector> ans;

vector row;

vector 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> permuteUnique(int[] nums) {

List> ans = new ArrayList<>();

Arrays.sort(nums);

backtrack(nums, ans, new boolean[nums.length], new LinkedList<>());

return ans;

}

private void backtrack(int[] nums, List> ans, boolean[] vis, Deque 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/ 博客原创~

精彩文章

 您阅读本篇文章共花了：