首页 > 代码库 > Leetcode#47 Permutations II

Leetcode#47 Permutations II

2024-11-15 11:31:02   203人阅读

原题地址

 

字典序模拟问题，枚举num的所有字典序。

假设已知序列seq，求下一个字典序序列：

1. 从序列seq右侧向左寻找第一个顺序对，即对于位置i，有seq[i] < seq[i+1]。如果找不到i，则说明已经没有下一个序列了，算法退出
2. 从序列seq右侧向左寻找第一个比seq[i]大的数，即seq[j] > seq[i]。肯定能找到这样一个j，因为j至少可以是i+1
3. 交换seq[i]和seq[j]
4. 将seq在位置i之后的部分倒置，即将seq[i+1..n-1]翻转

以上过程实际上就是在模拟手算下一个字典序的过程，如果不明白，模拟几组数据就明白了

PS：STL自带生成字典序的函数std::next_permutation

 

代码：排序+生成字典序

 1 int findLastAscendingPos(vector<int> &num) { 2   int i = num.size() - 2; 3   while (i >= 0 && num[i] >= num[i + 1]) 4     i--; 5   return i; 6 } 7  8 int findLastGreaterPos(vector<int> &num, int target) { 9   int i = num.size() - 1;10   while (i >= 0 && num[i] <= target)11     i--;12   return i;13 }14 15 vector<vector<int> > permuteUnique(vector<int> &num) {16   vector<vector<int> > pms;17   int n = num.size();18   sort(num.begin(), num.end());19 20   pms.push_back(num);21   while (true) {22     vector<int> next = pms.back();23     int i = findLastAscendingPos(next);24     if (i < 0) break;25     int j = findLastGreaterPos(next, next[i]);26     swap(next[i], next[j]);27     reverse(next.begin() + i + 1, next.end());28     pms.push_back(next);29   }30 31   return pms;32 }

 

Leetcode#47 Permutations II


联系
我们