将以下问题作为算法难题进行处理。引用了一些类似的解决方案(并在下面发布了其中一个)，尝试过并且它们有效。问题是，对于行“swap(num[i], num[k]);”，我们如何确保我们总是可以交换到以前从未尝试过的数字(例如，假设我们在当前迭代中将 1 与 2 交换for 循环，那么稍后我们有可能在相同级别/递归调用层的相同 for 循环的下一次迭代中将 2 换回 1)？我很困惑，因为我们通过引用传递 num，并且以后(较低级别/层)递归调用很可能会修改 num 的内容，这会导致我们已经评估过的数字交换回来。但是，我尝试过并且它适用于我所有的测试用例。想知道以下解决方案是否 100% 正确，或者碰巧通过了我的测试用例？ :)
这里是详细的问题陈述和我正在调试的代码，
给定一组可能包含重复项的数字，返回所有可能的唯一排列。
例如， [1,1,2] 有以下独特的排列: [1,1,2]、[1,2,1] 和 [2,1,1]
class Solution {
public:
void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
if (i == j-1) {
res.push_back(num);
return;
}
for (int k = i; k < j; k++) {
if (i != k && num[i] == num[k]) continue;
swap(num[i], num[k]);
recursion(num, i+1, j, res);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int> >res;
recursion(num, 0, num.size(), res);
return res;
}
};
提前致谢， 林
最佳答案
正如@notmyfriend 在评论中所说，num 实际上是在每次函数调用时复制的。
所以现在归结为:
- 在所有数组值中，选择一个作为第一个并将其放置在那里。
在每个值的循环中一次，然后递归地:- 在第一个值之后的所有值中，选择一个作为第一个并将其放在那里...
...等等，结合检查以过滤掉没有任何变化的交换，即。过滤掉重复项。
如果 num 是一个真正的引用，它将不再起作用(至少在没有额外步骤的情况下)。
例如。 1 1 2 是一个简单的反例，它会给出结果:
112, 121, 211, 112, 121
即。尽管进行了检查，但仍有重复项(并且可能存在
是根本不生成某些排列的示例)。
关于评论:
默认情况下，复制 C++ 中的每个正常函数参数
(正常 = 没有明确的引用符号 '&' 等)。
也许您正在考虑 C 风格的数组:本质上，传递给那里的是一个指针(指向第一个值)。指针被复制，但原始指针和复制指针都指向相同的内存位置。
虽然 std::vector 的目的(也)是包含一个数组，但 vector 本身是一个单一的类对象(它包含一个指向某处值的指针)。一个类可以自己定义它应该如何被复制(使用复制构造函数)。
从技术上讲， vector 类可以将复制实现为指针复制，那么它与将整个 vector 作为引用传递具有相同的效果；但是 C++ 的创建者想要保留复制语义，即。复制容器类应该制作一个所有值都重复的真实拷贝。
对于非复制，已经有引用了...
关于c++ - 对排列计算的唯一性感到困惑，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33626043/