字典序算法
背景
今天群里有人问了一个问题: 取出刚刚好大于自己的换位数(后来才知道这就是"字典序算法"),然后自己思考了一下用php简单实现了一下,没有详细验证,可能有bug.下面直接贴图
实现
代码
/**
* 字典序算法(取出刚刚好大于自己的换位数)
* 要刚刚大于,就需要尽量保持高位数字不动,所以从低位开始遍历
* 当低位的数字大于最近高位的数字,这个高位数就是需要被替换的
* 在已经遍历的低位数字中取出刚刚大于高位数的交换,并且把交换到低位的和剩下的全部低位数升序
* @param $number
* @return string
*/
public function getNumber($number)
{
$length = strlen($number);
$array = [];
for ($i = $length-1; $i > 0; $i--) {
//将已经遍历的低位数字全部放入一个临时的数组
array_push($array, $number[$i]);
//当低位的数字大于高位的数字
if ($number[$i] > $number[$i-1]) {
//在低位的所有数字中取出刚好大于高位的数字
$minNumber = $this->minNumber($array, $number[$i-1]);
//高低位交换
array_push($array, $number[$i-1]);//原来的高位数字放入低位临时数组中
$number[$i-1] = $minNumber;//低位取出的数字换给高位
//删除低位数组中已经换给高位的数字
$key = array_search($minNumber, $array);
unset($array[$key]);
//升序排列低位数组并还原成字符串
$array = $this->quickSort(array_values($array));
$newString = implode('', $array);
//返回高位数和升序排列后的低位数组成的新的数字
return substr($number, 0, $i).$newString;
}
}
return $number;
}
/**
* 取出刚好大于高位的数字
* @param array $array
* @param $number
* @return mixed
*/
public function minNumber(Array $array, $number)
{
$temp = [];
foreach ($array as $value) {
if ($value > $number) {
array_push($temp, $value);
}
}
return min($temp);
}
/**
* 快速排序法
* @param array $array
* @return array
*/
public function quickSort(Array $array){
$length = count($array);
if ($length <= 1) {
return $array;
}
//数组第一个值作为分隔值
$middle = $array[0];
$leftArray = []; //小于中间值
$rightArray = []; //大于中间值
for($i = 1; $i < $length; $i++) {
if ($middle > $array[$i]) {
array_push($leftArray, $array[$i]);
} else {
array_push($rightArray, $array[$i]);
}
}
//递归分割
$leftArray = $this->quickSort($leftArray);
$rightArray = $this->quickSort($rightArray);
//合并
return array_merge($leftArray, array($middle), $rightArray);
}
