LeetCode47——Permutations II

清疚 2022-08-09 12:41 253阅读 0赞

LeetCode47——Permutations II

含重复元素的全排列,仍然是套用了下一个全排列的方法。

跟上题一样,有时间补上递归解法。

代码:

  1. class Solution {
  2. private:
  3. void Swap(int &a, int &b)
  4. {
  5. int temp = a;
  6. a = b;
  7. b = temp;
  8. }
  9. bool Permutation(vector<int>&nums, int first, int last)
  10. {
  11. if (first == last)//长度为1
  12. return false;
  13. int i;
  14. i = last;
  15. while (1)
  16. {
  17. int ii = i;
  18. --i;
  19. //锁定两个相邻的元素
  20. if (nums[i] < nums[ii])//前一个元素小于后一个元素
  21. {
  22. int j = last;
  23. while (!(nums[i] < nums[j--]));//尾端往前找找到比nums[i]大的元素
  24. Swap(nums[i], nums[j+1]);
  25. reverse(nums.begin()+ii, nums.end());
  26. return true;
  27. }
  28. if (i == first)
  29. {
  30. reverse(nums.begin(),nums.end());
  31. return false;
  32. }
  33. }
  34. }
  35. public:
  36. vector<vector<int>> permuteUnique(vector<int>& nums) {
  37. vector<vector<int>>result;
  38. sort(nums.begin(),nums.end());
  39. result.push_back(nums);
  40. while(Permutation(nums,0,nums.size()-1))
  41. {
  42. result.push_back(nums);
  43. }
  44. // result.push_back(nums);
  45. return result;
  46. }
  47. };

发表评论

表情:
评论列表 (有 0 条评论,253人围观)

还没有评论,来说两句吧...

相关阅读