背景
今天群里有人問了一個問題:?取出剛剛好大于自己的換位數(shù)(后來才知道這就是"字典序算法"),然后自己思考了一下用php簡單實現(xiàn)了一下,沒有詳細驗證,可能有bug.下面直接貼圖
實現(xiàn)
代碼
/**
* 字典序算法(取出剛剛好大于自己的換位數(shù))
* 要剛剛大于,就需要盡量保持高位數(shù)字不動,所以從低位開始遍歷
* 當?shù)臀坏臄?shù)字大于最近高位的數(shù)字,這個高位數(shù)就是需要被替換的
* 在已經(jīng)遍歷的低位數(shù)字中取出剛剛大于高位數(shù)的交換,并且把交換到低位的和剩下的全部低位數(shù)升序
* @param $number
* @return string
*/
public function getNumber($number)
{
? ? $length = strlen($number);
? ? $array = [];
? ? for ($i = $length-1; $i > 0; $i--) {
? ? ? ? //將已經(jīng)遍歷的低位數(shù)字全部放入一個臨時的數(shù)組
? ? ? ? array_push($array, $number[$i]);
? ? ? ? //當?shù)臀坏臄?shù)字大于高位的數(shù)字
? ? ? ? if ($number[$i] > $number[$i-1]) {
? ? ? ? ? ? //在低位的所有數(shù)字中取出剛好大于高位的數(shù)字
? ? ? ? ? ? $minNumber = $this->minNumber($array, $number[$i-1]);
? ? ? ? ? ? //高低位交換
? ? ? ? ? ? array_push($array, $number[$i-1]);//原來的高位數(shù)字放入低位臨時數(shù)組中
? ? ? ? ? ? $number[$i-1] = $minNumber;//低位取出的數(shù)字換給高位
? ? ? ? ? ? //刪除低位數(shù)組中已經(jīng)換給高位的數(shù)字
? ? ? ? ? ? $key = array_search($minNumber, $array);
? ? ? ? ? ? unset($array[$key]);
? ? ? ? ? ? //升序排列低位數(shù)組并還原成字符串
? ? ? ? ? ? $array = $this->quickSort(array_values($array));
? ? ? ? ? ? $newString = implode('', $array);
? ? ? ? ? ? //返回高位數(shù)和升序排列后的低位數(shù)組成的新的數(shù)字
? ? ? ? ? ? return substr($number, 0, $i).$newString;
? ? ? ? }
}
? ? return $number;
}
/**
* 取出剛好大于高位的數(shù)字
* @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;
? ? }
? ? //數(shù)組第一個值作為分隔值
? ? $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);
}
