31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

蛮讨厌这种题目的, 要自己先找出规律, 然后再implement, 基本上都会卡在找出规律上.

  1. 观察到: 当array是整个倒序排列/递减的时候, 不存在next permutation
  2. 然后想到从后往前找第一个i使得nums[i] > nums[i - 1] => 然后就不知道怎么办了

给定一个sort的 nums array, 它的计算next permutations的过程其实是以nums[i]为分割点, [i, len)这个区域内递减 -> 这个区域不断扩大至[0, len)的一个过程.

  1. 当有一个nums[i]使得[i, len - 1)递减且nums[i - 1] < nums[i]的时候 => 此时nums[i]是一个凸点
  2. [i, len-1)这个区间递减, 这个区间内的数字就不存在next permutation了 => 开始考虑nums[i - 1]
  3. 再回头重新想这个next permutation的定义是next permutation that is lexicographically larger than current
    • 所以next permutation一定是: [0, i - 2] 不变, 改变[i - 1, len - 1)
    • 且 nums[i - 1] 上应该放 [i, len - 1)中比nums[i - 1]大的数字中最小的那个 => swap这2个数字
  4. 把nums[i - 1]与[i, len - 1)中比nums[i - 1]大的数字中最小的那个swap之后, [i, len - 1)会发生什么变化?
    • [i, len - 1)的递减性是不变的
  5. swap了nums[i - 1]之后的next permutation/最小的lexicographical order是什么?
    • [0, i - 1]已经满足是属于后n个permutation中的一个了
    • 当[i, len - 1)是递增的时候, 这样整个一个新的数组才是next permutation
  6. 在这之后, 继续从后扫描找到第一个凸点 => 目前不存在, 因为后面是递增, 所以nums[len - 1]算是凸点, 从它开始重复整个步骤
  7. 直到整个nums都是递减不存在凸点了

Reference: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

代码写下来其实还行, 有些细节要注意

  1. 指针p从后往前找到凸点 index
  2. 如果凸点index p == 0 => 没有next permutation, reverse整个array, 否则进行step 3
  3. 定nums[p - 1]为pivot to be swapped
  4. 在[p, len - 1)中找到最小的比nums[p - 1]大的数字的index target, 没有的话返回p => binary search
    • NOTE: 这里可能不存在. 当p == len - 1的时候
  5. swap(p - 1, target)
  6. reverse [p, len - 1] => using swap

所以里面的核心code有三个: 1) one pointer 2) reverse with swap 3) binary search

要注意写在一个递减的array里面找到第一个比target大的数字的index

TimeComplexity

  • find p -> O(N)
  • findFirstLargest(logN)
  • O(N + logN) ~ O(N)

Space: O(1)

 public void nextPermutation(int[] nums) {     if (nums.length <= 1) return;      int len = nums.length;     int p = len - 1;     while(p > 0 && nums[p] <= nums[ p - 1]) {         p --;     }     if (p == 0) {         reverse(nums, 0);         return;     }      int target = findFirstLarger(nums[p - 1], nums, p, len - 1);     swap(p - 1, target, nums);     reverse(nums, p); }  private void reverse(int[] nums, int s) {     int e = nums.length - 1;     while(s < e) {         swap(s, e, nums);         s ++;         e --;     } }  private void swap(int a, int b, int[] nums) {     int tmp = nums[a];     nums[a] = nums[b];     nums[b] = tmp; }  // find the smallest element that is > target, if not return start private int findFirstLarger(int target, int[] nums, int start, int end) {     int s = start, e = end, m = s;     while(s + 1 < e) {         m = s + (e - s) / 2;         if (nums[m] > target)             s = m;         else             e = m - 1;     }     if (nums[e] > target) return e;     return s; }
This free site is ad-supported. Learn more
​