一道算法題（next smaller）

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

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

題目如下：

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

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

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

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

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

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

舉例分析：

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

為什么這樣做？

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

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

總結(jié)：

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

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

下面是寫(xiě)得不怎么樣的代碼：

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);
}