算法
枚举每个位置上放哪个数
以[1,1,2]为例:
[ , , ]
/ |
/ |
[1, , ] [2 ,, ]
/ \ |
/ \ |
[1,1, ] [1,2, ] [2,1, ]
| | |
[1,1,2] [1,2,1] [2,1,1]
时间复杂度: O(n*n!)
总空间复杂度: O(n!)
额外空间复杂度: O(n)
C++代码
class Solution {
public:
static vector<vector<int>> permuteUnique(vector<int> &nums) {
const int n = static_cast<int>(nums.size());
vector<vector<int>> res;
if (n == 0) {
return res;
}
sort(nums.begin(), nums.end());
vector<int8_t> numIndexVisited(n);
vector<int> path(n);
permuteDfs(nums, numIndexVisited, path, 0, res);
return res;
}
private:
static void permuteDfs(const vector<int> &nums, vector<int8_t> &numIndexVisited,
vector<int> &path, const int pathIndex, vector<vector<int>> &res) {
const int n = static_cast<int>(nums.size());
if (pathIndex == n) {
res.push_back(path);
return;
}
for (int numIndex = 0; numIndex < n; ++numIndex) {
if (numIndex > 0 && numIndexVisited[numIndex - 1] && nums[numIndex - 1] == nums[numIndex]) {
continue;
}
if (!numIndexVisited[numIndex]) {
numIndexVisited[numIndex] = true;
path[pathIndex] = nums[numIndex];
permuteDfs(nums, numIndexVisited, path, pathIndex + 1, res);
numIndexVisited[numIndex] = false;
}
}
}
};
Java代码
class Solution {
public static List<List<Integer>> permuteUnique(final int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
final int n = nums.length;
Arrays.sort(nums, 0, n);
boolean[] numIndexVisited = new boolean[n];
int[] path = new int[n];
permuteDfs(nums, numIndexVisited, path, 0, res);
return res;
}
private static void permuteDfs(final int[] nums, final boolean[] numIndexVisited, final int[] path, final int pathIndex, final List<List<Integer>> res) {
final int n = nums.length;
if (pathIndex == n) {
final List<Integer> tmpList = new ArrayList(n);
for (final int num : path) {
tmpList.add(num);
}
res.add(tmpList);
return;
}
for (int numIndex = 0; numIndex < n; ++numIndex) {
if (numIndex > 0 && numIndexVisited[numIndex - 1] && nums[numIndex - 1] == nums[numIndex]) {
continue;
}
if (!numIndexVisited[numIndex]) {
numIndexVisited[numIndex] = true;
path[pathIndex] = nums[numIndex];
permuteDfs(nums, numIndexVisited, path, pathIndex + 1, res);
numIndexVisited[numIndex] = false;
}
}
}
}
Python3代码
Go代码
未完待续
这题如果存一个hashset来避免重复 和你这个解法比起来 时间复杂度会差不多吗
public List[HTML_REMOVED]> permuteUnique(int[] nums) {
List[HTML_REMOVED]> ans = new LinkedList<>();
List[HTML_REMOVED] path = new LinkedList<>();
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
dfs(ans, path, nums, visited, 0);
return ans;
}
if (numIndex > 0 && numIndexVisited[numIndex - 1] && nums[numIndex - 1] == nums[numIndex])
不太懂这个条件过滤掉的情况,求详细解答哈~
dfs函数里的条件判断 numIndexVisited[numIndex - 1]应当为false时才continue吧?
numIndexVisited[numIndex - 1] 表示 nums[numIndex-1] 用过了