求离一正整数最近的大于自身的“换位数”(源自程序员小灰)作者:luke

给定一个正整数,实现一个方法来求出离该整数最近的大于自身的“换位数”。

什么是换位数呢?就是把一个整数各个数位的数字进行全排列,从而得到新的整数。例如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];
时间:2018-4-9 分类:练习