求离一正整数最近的大于自身的“换位数”(源自程序员小灰)
给定一个正整数,实现一个方法来求出离该整数最近的大于自身的“换位数”。
什么是换位数呢?就是把一个整数各个数位的数字进行全排列,从而得到新的整数。例如53241和23541。
小灰也不知道这种经过换位的整数应该如何称呼,所以姑且称其为“换位数”。
题目要求写一个方法来寻找最近的且大于自身的换位数。比如下面这样:
输入12345,返回12354
输入12354,返回12435
输入12435,返回12453
什么是换位数呢?就是把一个整数各个数位的数字进行全排列,从而得到新的整数。例如53241和23541。
小灰也不知道这种经过换位的整数应该如何称呼,所以姑且称其为“换位数”。
题目要求写一个方法来寻找最近的且大于自身的换位数。比如下面这样:
输入12345,返回12354
输入12354,返回12435
输入12435,返回12453
注:看题之后的第一想法是,是先对此数进行拆分组合,得到这几个数字所有的全排列,然后对其升序排序,得到自小到大的排序序列,此正整数后面的数即为大于它的“换位数”。
$t = '1324'; $r = preg_match_all('#\d#', $t, $m); $r = []; foreach($m[0] as $v){ $r[] = (int)$v; } sort($r); //保证初始数组是有序的 $last = count($r) - 1; //$r尾部元素下标 $x = $last; $count = 1; //组合个数统计 $fullArr[] = implode('', $r); while (true) { $y = $x--; //相邻的两个元素 if ($r[$x] < $r[$y]) { //如果前一个元素的值小于后一个元素的值 $z = $last; while ($r[$x] > $r[$z]) { //从尾部开始,找到第一个大于 $x 元素的值 $z--; } /* 交换 $x 和 $z 元素的值 */ list($r[$x], $r[$z]) = array($r[$z], $r[$x]); /* 将 $y 之后的元素全部逆向排列 */ for ($i = $last; $i > $y; $i--, $y++) { list($r[$i], $r[$y]) = array($r[$y], $r[$i]); } $fullArr[] = implode('', $r); $x = $last; $count++; } if ($x == 0) { //全部组合完毕 break; } } asort($fullArr); var_dump($fullArr); $index = array_search('1324', $fullArr); echo PHP_EOL,'next ',$fullArr[$index+1];
« 1984
|
给PHP关联数组的头部增加一项»