[leetcode] Next Permutation | 用同样的digit set组成的immediate next的数

Posted by: lexigrey on: August 3, 2013

• In: leetcode
• 3 Comments

example: {1, 3, 1, 4, 2, 0} => {1, 3, 2, 0, 1, 4}

这题有点类似于CC上做的“同样的0和1组成的immediate next“那道题。曾经被问过原题两次，都做出来了，但是这次居然要看答案才会！！还是不扎实啊。。

和CC那道题的区别：100110 – 从右往左找第一个”后面有1的0“，然后变成1，后面自排就行了。但是这道题是数字，难说“从右往左找第一个比谁大的呢？”——其实找到一个比右边的某个数小的就行了，这样保证找到的这位i还算比较低位（从后往前找的嘛），然后右面那个比它大的数j可以和它swap，剩下的那些数在右边排列成升序就行了。

但是这么做，发现不能不用额外空间还O(n)（最后那些数要sort，要么费时间要么费空间）。于是看别人答案，是”从右开始找第一个升序排列的紧挨着的两个数i – 1和i“，说明越过的最右边的都是降序的。然后让从第i位（这里是第二个1）开始往后找，找到j使j是i的immediate next（arr[j] > arr[i] &&arr[j] 小于其他右边的>arr[j]的数，这里是2）。然后i, j swap，  这样arr[i]就到了”他应该属于的位置（j的位置）“，此时右边这些就正好降序排列了，可以直接两两swap使O(n)的升序sort成功。

private void getNext(int[] arr) {
  int pivot = -1;
  for (int i = arr.length - 1; i > 0; i--) {
    if (arr[i] > arr[i - 1]) {
      pivot = i - 1;
      break;
    }
  }
  if (pivot < 0) {
    arrangeToIncreaseOrder(arr, 0);
    return;
  }
  // the index of the number that is immediate next of pivot
  int nextToPivot = pivot + 1;
  for (int i = nextToPivot + 1; i < arr.length; i++) {
    if (arr[i] > arr[pivot] && arr[i] <= arr[nextToPivot])
      nextToPivot = i;
  }
  swap(arr, pivot, nextToPivot);
  // arrange arr to be increase from index i
  arrangeToIncreaseOrder(arr, pivot + 1);
}

Tags: hard, math