题解 | #有重复项数字的所有排列#

NC42 有重复项数字的所有排列

题意分析：

生成所给数字的所有排列。

这一题与JZ27字符串的排列基本一样将字符换成了数字

题解一（暴力回溯）：

回想一下高中所学的排列组合知识：有3个红球，2个白球，1个黑球，请问有多少中排列方式。

我们的计算方式是：一个有6个位置，先选择3个位置放红球，再从剩下的3个位置中选择2个位置放白球，最后剩下一个位置放黑球。总共的排列数有种。

我们这题就是要用代码生成这些排列。

我们从左往右依次填入给定的数字，每个字符使用一次。

当我们使用完了所有的数字，那么就可以将生成的数组加入到最终结果中。
当我们没有使用完数字，考虑下一步应该使用什么字符呢？之前使用过的数字不能再使用了。我们可以对使用过的数字做一个标记，表示已经使用过了。然后使用没有标记过的数字。

依据之前提到放球的解答，我们应该把不同的字符做一个统计，然后把他们放到一些位置中。我们使用map<char,int>m给不同的字符做标记。如果字符i使用了一次。m[i]--。相应的当m[i]==0时，表示没有字符i可供使用。

算法实现如下：

void backtrack(map<int, int> &m, vector<vector<int>> &ret, vector<int> &tmp, int n) {
    if (tmp.size() == n) {
        ret.push_back(tmp);//当最后生成的tmp长度等于n即可添加到最后结果中，n指的是输入数组长度，
    }
    for (auto &i:m) {
        if (i.second > 0) {//当i.second>0,表示有数字i.first可以被使用
            i.second--;//使用一次数字i.first,i.second--;
            tmp .push_back(i.first);//加到生成的数组中
            backtrack(m, ret, tmp, n);//下一步生成tmp
            tmp.pop_back();
            i.second++;//上面回溯结束后，使用过的i.first拿出去，又可以被使用，因此tmp弹出最后一个元素，i.second++
        }
    }
}

vector<vector<int> > permuteUnique(vector<int> &num) {
    map<int, int> m;
    for (auto& i : num) {
        m[i]++;
    }
    vector<vector<int>> ret;
    vector<int> tmp;
    backtrack(m, ret, tmp, num.size());
    return ret;
}

时间复杂度：与数组中数字的种类有关。非确切上界为。

空间复杂度：。我们需要 栈空间进行回溯。

题解二(取巧）：

C++有个叫next_permutation函数。可以参考[官方文档](next_permutation - C++ Reference (cplusplus.com))，了解去功能和用法。简单的来说他可以帮忙生成下一个排列。因此我们不断的使用这个函数求下一个排列即可。

vector<string> Permutation(vector<int>&num) {
    sort(num.begin(), num.end());
    vector<vector<int>>ret;
    ret.push_back(num);
    while(next_permutation(num.begin(), num.end())){
        ret.emplace_back(num);
    };
    return ret;
}

题解三（自己实现一个next_permutation）:

bool next_Permutation_Of_Own(vector<int> &num) {
    int i = num.size() - 2;
    while (i >= 0 && num[i] >= num[i + 1]) {
        i--;
    }
    if (i < 0) {
        return false;
    }
    int j = num.size() - 1;
    while (j >= 0 && num[i] >= num[j]) {
        j--;
    }
    swap(num[i], num[j]);
    reverse(num.begin() + i + 1, num.end());
    return true;
}

用 nextPermutation_of_Own(vector<int>&nums)代替内置的next_permutation。</int>

时间复杂度：。

空间复杂度：。仅仅在sawp时候用到额外的一个变量。