LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 这就是 std::next_permutation 的功能

class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    next_permutation(nums.begin(), nums.end());
  }
};

• 其原理为，找到最大满足 nums[i] < nums[i + 1] 的索引 i，将 nums[i] 右侧元素排序后，在右侧元素中找到第一个大于 nums[i] 的数，与 nums[i] 交换

23541 => 找到 3 < 5 => 排序 3 右侧
23145 => 将 3 与右侧第一个大于 3 的数交换
24135

54321 => 找不到则说明无下一排列，翻转即可

• 解法如下

class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    if (nums.size() <= 1) {
      return;
    }
    for (int i = nums.size() - 1; i > 0; --i) {
      if (nums[i - 1] < nums[i]) {
        sort(nums.begin() + i, nums.end());
        for (int j = i; j < nums.size(); ++j) {
          if (nums[j] > nums[i - 1]) {
            swap(nums[i - 1], nums[j]);
            return;
          }
        }
      }
    }
    reverse(nums.begin(), nums.end());
  }
};