Mathematik hinter Leetcode-Problem 47 Permutationen II
-
29-09-2020 - |
Frage
Bitte sagen Sie mir, warum der Ausdruck i>0 && nums[i] == nums[i-1] && !used[i-1]
arbeitet daran, eindeutige Permutationen zu erhalten.Und welche Mathematik steckt dahinter?
Das Problem ist wie folgt:
Geben Sie bei einer Sammlung von Zahlen, die möglicherweise Duplikate enthalten, alle möglichen eindeutigen Permutationen zurück.Beispiel:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Hier ist der Code:
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
vector<int> temp;
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backtrack(nums, temp, result, used);
return result;
}
void backtrack(vector<int>& nums, vector<int>& temp, vector<vector<int>>& result, vector<bool>& used){
if(temp.size() == nums.size()){
result.emplace_back(temp);
}else{
for(int i=0; i<nums.size(); i++){
if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
temp.push_back(nums[i]);
backtrack(nums, temp, result, used);
used[i] = false;
temp.pop_back();
}
}
}
};
Lösung
(1) Sie sortieren den Vektor so, dass im Vektor nacheinander doppelte Werte vorhanden sind.
(2) Nun kommen wir zur Logik hinter dieser Bedingung:
- Da der Vektor Duplikate enthalten kann, sollten wir darauf achten, nicht dieselbe Sequenz zu wiederholen, indem wir erneut mit demselben Element beginnen (Duplikat).
- Beispiel :
1,1,2
(beginnen mitfirst
eins) und 1,1,2 (beginnend mitsecond
eins) => beide sind gleich (wir sollten sicherstellen, dass das nicht passiert)
- Beispiel :
Beispiel:In [1, 1, 2]
Wenn das erste Element in der Sequenz als 1 ausgewählt wird, sollten wir sicherstellen, dass wir keine weitere Sequenz erstellen, die mit einer weiteren 1 (Duplikat des Elements) beginnt.
Dazu müssen wir die Schleife für alle aufeinanderfolgenden doppelten Elemente überspringen.
In Ihrem Fall überprüfen wir nach dem Erstellen einer Sequenz, die mit der ersten 1 beginnt, beim zweiten Eintritt in die Schleife, ob das aktuelle Element ein Duplikat ist
nums[i] == nums[i - 1]
(Dies reicht aus, da Sie den Vektor bereits sortiert haben) und ob das aktuelle Element das erste Element der Sequenz ist!used[i - 1]
.- In Ihrem Fall kann aufgrund dieser Bedingung das zweite nicht das erste Element der Sequenz sein.