一道算法題（next smaller）

mgckid 發(fā)布于2019-08-20 13:32 / 722人閱讀

摘要：從位向右，找到比小的最大的那個數(shù)，并與交換。交換后，把位向右注意是的，不是的值的所有數(shù)字降序排列。對于來說，從右向左可以分割為，，，這三種情況都是最小排列。

題目如下：

給定某一個正整數(shù)，組成這個數(shù)的數(shù)字不變，返回下一個比它小的數(shù)，如：

nextSmaller(21) == 12
nextSmaller(531) == 513
nextSmaller(907) == 790
nextSmaller(51226262651257) == 51226262627551

如果沒有下一個比它小的數(shù)字，或者下一個比它小的數(shù)字以0開頭，則返回-1，如：

nextSmaller(9) == -1
nextSmaller(111) == -1
nextSmaller(135) == -1
nextSmaller(1027) == -1 // 0721以0開頭，所以返回-1

算法描述（找到下一個比它小的數(shù)）：

1.find pivot：這個數(shù)從右往左，一位位地來比較，如果第i位的數(shù)字，比第i+1位的數(shù)字大，則把第i位的數(shù)字置為pivot（標志位）。
2.swap：從pivot位向右，找到比pivot小的最大的那個數(shù)，并與pivot交換。
3.sort：交換后，把pivot位向右（注意是pivot的index，不是pivot的值）的所有數(shù)字降序排列。
這樣，新得到的數(shù)就是下一個比它小的數(shù)。

舉例分析：

比如我們拿54123來分析。
1.find pivot：從最右邊的3來看，因為3沒有第i+1位數(shù)字（3沒有右邊），所以左移一位到2；2比右邊的3小，所以繼續(xù)左移一位到1；同理，1也比2要小，所以繼續(xù)左移一位到4；4比1要大了，那么把4置為pivot，這時停止。
2.swap：現(xiàn)在4是pivot，那么從4向右，有1，2，3三個數(shù)字，并且都比4小，這其中3是最大的，所以把4和3的位置交換，得到53124。
3.sort：交換后，pivot位上是3，把3往右的所有數(shù)字降序排列，得到53421，這就是下一個比54123小的數(shù)。

為什么這樣做？

下面是我自己思考的為什么，不一定對。

對于每個數(shù)，它最小的排列只有1種情況，就是權(quán)位從高到低，數(shù)字從小到大排列。
比如123的最小排列就是123。
對于54123來說，從右向左可以分割為3，23，123，這三種情況都是最小排列。
也就是說，如果我們只對3或者23或者123進行重組，是沒有變化的。
于是再向左進行分割，得到5和4123，發(fā)現(xiàn)4123已經(jīng)不再是最小排列了，換句話說4123肯定有下一個比它小的數(shù)，就把4標記出來，對4123進行重組。
怎么重組呢？最高的權(quán)位，放上比4稍小的，也就是3，然后對于3xxx的后三位，放上值最大的情況，就是412的降序排列421，這樣就能保證“3421是4123的上一個數(shù)”。

總結(jié)：

這個算法一句話總結(jié)：對于某個數(shù)，從右向左找它的子列，如果子列是最小排列，那子列沒法重組，繼續(xù)向右；如果子列不是最小排列，就對子列進行重組。

感覺算法里，“分治”加“pivot（標志位）”的解法很常用啊，把復(fù)雜情況分成最簡單的子情況，如果符合規(guī)律，那么子情況擴充，如果不符合規(guī)律，那么置上標志位，再進行考慮。

下面是寫得不怎么樣的代碼：

function nextSmaller(num) {
  var arr = [];
  (num + "").split("").forEach(function (val) {
    arr.push(parseInt(val));
  });
  // 1st: find the pivot, if digit is greater than its right digit, it becomes a pivot
  var pivot = -1;
  for(var i = arr.length - 2; i >= 0;i--) {
    if (arr[i] > arr[i + 1]) {
      pivot = i;
      break;
    }
    if (i == 0) {
      return -1;
    }
  }
  // 2nd: find the least less than the pivot, and swap them
  var swap = -1;
  for (i = pivot + 1;i < arr.length;i++) {
    if (swap < 0) {
      if (arr[i] < arr[pivot]) {
        swap = i;
      }
    } else {
      if (arr[i] < arr[pivot] && arr[i] > arr[swap]) {
        swap = i
      }
    }
  }
  var _mem;
  _mem = arr[pivot];
  arr[pivot] = arr[swap];
  arr[swap] = _mem;
  if (arr[0] == 0) {
    return -1;
  }
  // 3rd: sort the right of pivot, decreasingly
  var firstArray = arr.slice(0, pivot + 1);
  var secondArray = arr.slice(pivot + 1);
  secondArray.sort(function (a, b) {
    return b -a;
  });
  // 4th: return val
  var result = (firstArray.concat(secondArray)).join("");
  if (result == num){
    return - 1
  }
  return parseInt(result);
}