一道算法题（next smaller）

mgckid 发布于2019-08-20 13:32 / 692人阅读

摘要：从位向右，找到比小的最大的那个数，并与交换。交换后，把位向右注意是的，不是的值的所有数字降序排列。对于来说，从右向左可以分割为，，，这三种情况都是最小排列。

题目如下：

给定某一个正整数，组成这个数的数字不变，返回下一个比它小的数，如：

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

如果没有下一个比它小的数字，或者下一个比它小的数字以0开头，则返回-1，如：

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

算法描述（找到下一个比它小的数）：

1.find pivot：这个数从右往左，一位位地来比较，如果第i位的数字，比第i+1位的数字大，则把第i位的数字置为pivot（标志位）。
2.swap：从pivot位向右，找到比pivot小的最大的那个数，并与pivot交换。
3.sort：交换后，把pivot位向右（注意是pivot的index，不是pivot的值）的所有数字降序排列。
这样，新得到的数就是下一个比它小的数。

举例分析：

比如我们拿54123来分析。
1.find pivot：从最右边的3来看，因为3没有第i+1位数字（3没有右边），所以左移一位到2；2比右边的3小，所以继续左移一位到1；同理，1也比2要小，所以继续左移一位到4；4比1要大了，那么把4置为pivot，这时停止。
2.swap：现在4是pivot，那么从4向右，有1，2，3三个数字，并且都比4小，这其中3是最大的，所以把4和3的位置交换，得到53124。
3.sort：交换后，pivot位上是3，把3往右的所有数字降序排列，得到53421，这就是下一个比54123小的数。

为什么这样做？

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

对于每个数，它最小的排列只有1种情况，就是权位从高到低，数字从小到大排列。
比如123的最小排列就是123。
对于54123来说，从右向左可以分割为3，23，123，这三种情况都是最小排列。
也就是说，如果我们只对3或者23或者123进行重组，是没有变化的。
于是再向左进行分割，得到5和4123，发现4123已经不再是最小排列了，换句话说4123肯定有下一个比它小的数，就把4标记出来，对4123进行重组。
怎么重组呢？最高的权位，放上比4稍小的，也就是3，然后对于3xxx的后三位，放上值最大的情况，就是412的降序排列421，这样就能保证“3421是4123的上一个数”。

总结：

这个算法一句话总结：对于某个数，从右向左找它的子列，如果子列是最小排列，那子列没法重组，继续向右；如果子列不是最小排列，就对子列进行重组。

感觉算法里，“分治”加“pivot（标志位）”的解法很常用啊，把复杂情况分成最简单的子情况，如果符合规律，那么子情况扩充，如果不符合规律，那么置上标志位，再进行考虑。

下面是写得不怎么样的代码：

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

GPU云服务器云服务器 javascript算法题字符串算法题最难的算法题 java有趣算法题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/81103.html

每日一道算法题

摘要：遇到的坑刚拿到这道题就直接做了这样的判断，可是万一是这个判断就是错误的了。思路二上述算法遍历了两次链表，还额外申请了一个数组空间，效率不高，不如直接就地反转链表，更改每个节点自身的指针。 2018.10.14 来源：剑指offer 题目：反转链表输入一个链表，反转链表后，输出新链表的表头。思路一：把所有链表内容都输入到一个数组，再次遍历链表，得到数组反转后的值，最后输出原来的head...

The question 2019-08-23 12:21 评论0 收藏0
从一道前端面试题谈起

摘要：但是题目非要弄成链表的形式，说实在的，我真没有见过前端什么地方还需要用链表这种结构的除了面试的时候，所以说这种题目对于实际工作是没什么用处的，但是脑筋急转弯的智商题既然这样出了，我们就来看看怎么解决它吧。今天在知乎上看到一个回答《为什么前端工程师那么难招？》，作者提到说有很多前端工程师甚至连单链表翻转都写不出来。说实话，来面试的孩子们本来就紧张，你要冷不丁问一句单链表翻转怎么写，估计...

darkbaby123 2019-08-23 17:53 评论0 收藏0
每日一道算法题 - LongestWord(easy-1)

摘要：规则使用语言，让函数获取传递的参数并返回字符串中的最大单词。忽略字符串中标点符号并假设不会为空。测试用例思路通过过滤字符串，并把字符串根据空格符转换成字符串数组通过循环把获取字符串数组中的长度最长的字符串虽然都是很简单的算法，每个都只需5分钟左右，但写起来总会遇到不同的小问题，希望大家能跟我一起每天进步一点点。更多的小算法练习，可以查看我的文章。规则 Using the JavaS...

plokmju88 2019-08-22 18:35 评论0 收藏0
[Java] 关于一道面试题的思考

摘要：对于这种会退出的情况，数组显然不能像链表一样直接断开，因此采用标记法先生成一个长度为的布尔型数组，用填充。中对整个进行遍历才能得到此时数组中的数量。文中的速度测试部分，时间是通过简单的 System.currentTimeMillis() 计算得到的，又由于 Java 的特性，每次测试的结果都不一定相同，对于低数量级的情况有 ± 20 的浮动，对于高数量级的情况有的能有 ± 10...

rozbo 2019-08-15 14:50 评论0 收藏0
Java数据结构与算法——链表（面试）

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。指针反转实现链表反转代码反转链表获取当前下下个元素测试代码部分用到了上篇文章数据结构与算法链表的代码段，请移步获取。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文是上篇文章Java数据结构与算法——链表的扩展篇，介绍链表的特点，使用场景、链表的性能分析以...

keke 2019-08-16 11:08 评论0 收藏0