一道算法题(next smaller)

2017-01-13 10:49:08来源:segmentfault作者:隐约雷鸣人点击

题目如下:

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


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

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台