【Check 86】2024-05-30 -31. 下一个排列

[larscheng]

31. 下一个排列

[larscheng]

思路

• 从后往前找第一个相邻升序的元素对(i,j)，nums[i]<nums[j]
• 此时j往后的元素均为降序，[j,end]
• 要找的下一个排列，要比够距离当前足够小，并大于当前数列
• 需要从[j,end]中找第一个满足nums[k]>nums[i]的k元素与i交换位置
• 交换后，[j,end]的元素要调整为升序，保证足够小切大于当前数列

• 如果最开始找不到元素对(i,j)，nums[i]<nums[j]，则直接将所有元素调整为升序

  代码

  
  public void nextPermutation(int[] nums) {
      int length = nums.length;
      int i = length - 1;
      int j = length - 1;
      //找相邻升序对 nums[i]<nums[j]
      for (int k = length-2; k >=0; k--) {
          if (nums[k]<nums[k+1]){
              i = k;
              j = k+1;
              break;
          }
      }
      if (i==j){
          reverse(nums, 0, length-1);
      }
      //从[j,end]中 由后向前找一个大于nums[i]的数
      for (int k = length-1; k >=j ; k--) {
          if (nums[k]>nums[i]){
              int temp = nums[i];
              nums[i] = nums[k];
              nums[k] = temp;
              break;
          }
      }
      //[j,end]为降序，下一个排列必须足够小，所以要将[j,end]转为升序
      reverse(nums, j, length-1);
  
  }
  
  private void reverse(int[] nums, int left, int right) {
      while (left <right){
          int temp = nums[left];
          nums[left] = nums[right];
          nums[right] = temp;
          left++;
          right--;
      }
  }

### 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)