剑指Offer - PHP丑数
题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
分析
- 丑数的递推性质：丑数只包含因子 2，3，5，因此有
丑数 = 某较小丑数 × 某因子(例如：10=5×2)。
根根据递推性质，丑数 Xn 只可能是以下三种情况其中之一（数组下标 a, b, c 为未知数）：
例子：求第四个丑数
- 定义一个数组
res存放丑数，初始化数组的第一个元素为 1。指针 a b c初始化为 0。
此时，Xa = Xb = Xc = 1。
数组第二个元素的值选择三种情况中的最小值，并将其对应的因子下标加 1，即 a = 1。结果如下所示。
此时，Xa = 2，Xb = Xc = 1。
数组第三个元素的值选择三种情况中的最小值，并将其因子对应的下标加 1，即 b = 1。结果如下所示。
此时，Xa = Xb = 2，Xc = 1。
- 数组第四个元素的值选择三种情况中的最小值，并将其因子对应的下标加 1，即 a = 2。结果如下所示。
此时，Xa = 3，Xb = 2，Xc = 1。
代码
<?php
namespace app\index\controller;
class Test
{
//测试
public function test()
{
$index = 4;
$this->GetUglyNumber_Solution($index);
}
function GetUglyNumber_Solution($index)
{
if ($index == 0) return 0;
$a = $b = $c = 0; // 定义三个指针来维持最小的 a b c
$res = [1]; // 第一个丑数为 1
for ($i = 1; $i < $index; $i++) {
$tmp_a = $res[$a] * 2;
$tmp_b = $res[$b] * 3;
$tmp_c = $res[$c] * 5;
$res[$i] = min($tmp_a, $tmp_b, $tmp_c); // 选择三种情况的最小值
// 如果 tmp 有相等的值，则都会加1
if ($tmp_a == $res[$i]) $a++;
if ($tmp_b == $res[$i]) $b++;
if ($tmp_c == $res[$i]) $c++;
}
return end($res);
}
}
关于 LearnKu
粤公网安备 44030502004330号