2019-12-24 吴亲库里 库里的深夜食堂
给定一个非排序的整形数组，让我们寻找消失的第一个正整数。
****
常规做法就是很简单的暴力破解，从1开始循环到数组的个数，发现不在直接返回，否则返回个数+1.
/**
* @param Integer[] $nums
* @return Integer
*/
function firstMissingPositive($nums) {
$start=1;
$n=count($nums);
while($start<=$n){
if(!in_array($start,$nums)) return $start;
$start++;
}
return $n+1;
}但是这并不能满足题目要求，运行时间O(n),空间O(1)。难度有点大，直到看到一个牛逼的思路。
首先我们并不在乎小于等于0的数，以及大于n的数(如果从 1-n 中间都不缺，那么返回的肯定是 n+1),第一步，先排除掉不存在1的情况，这种情况肯定返回1。下一步如果数组只有1位的话那么肯定返回2(结合上一个条件思考下)。接下来把小于等于0或者大于 n 的数都用1来替代。这时候我们得到的必然都是 1-n 值的数组。最后遍历一遍数组，把索引位置 $elem 的值 $nums[$elem] 作为键，修改$nums[$nums[$elem]] 的值符号为绝对值的 -(即修改成负数)。为什么加绝对值，我们需要保证有重复数字的时候只改变了一次。最后举个例子，如果$nums[1] 是负数，说明1已经存在在当前数组中，如果 $nums[2] 是正数，说明2不存在数组中，2就是我们要寻找的缺失的第一个整数。具体看代码实现
/**
* @param Integer[] $nums
* @return Integer
*/
function firstMissingPositive($nums)
{
$n = count($nums);
$oneCount = 0;
for ($i = 0; $i < $n; $i++) {
if ($nums[$i] == 1) $oneCount++;
}
//第一遍先排除1 没有1 返回1
if ($oneCount == 0) {
return 1;
}
//只有一位那么说明那位是1 返回2
if ($n == 1) return 2;
//把小于等于0或者大于n的数都转换成1
for ($i = 0; $i < $n; $i++) {
if ($nums[$i] <= 0 || $nums[$i] > $n) {
$nums[$i] = 1;
}
}
//如果发现了一个数字 $temp 改变第 $temp 个元素的符号 修改成 -
//这样的话
//例如，如果 nums[1] 是负数表示在数组中出现了数字 `1`
// 如果 nums[2] 是正数 表示数字 2 没有出现
for ($i = 0; $i < $n; $i++) {
$temp = abs($nums[$i]);
if ($temp == $n) {
$nums[0] = -abs($nums[0]);
} else {
$nums[$temp] = -abs($nums[$temp]);
}
}
//第一个整数就是缺失的数
for ($i = 1; $i < $n; $i++) {
if ($nums[$i] > 0) return $i;
}
//因为没有下标n 用位置0 代替
if ($nums[0] > 0) return $n;
//都没有那么就是n+1
return $n + 1;
}其实上面的解题思路就是一个动态规划的过程。动态规划最重要的两步：1 是状态的定义，即上面的这两个定义:
$left[0] = $height[0];
$right[$size - 1] = $height[$size - 1];第二步就是状态转移方程，即上面的
$left[$i] = max($left[$i - 1], $height[$i]);
$right[$i] = max($right[$i + 1], $height[$i]);其实动态规划就像是开启了上帝的视角，每次都能获取到全局的情况。经常用来解最优，最近，最少这类题目。你再进一步分析，好像动态规划的思想就是一个空间换时间的方案。第一个解的时间是 O (n 的平方)，空间就一个变量 O (1)。再来看第二道解，时间是 O (n)，空间是 O (n)。本质上来说就是空间换时间的方案。最后其实这道题还有其他能解的方案。。。。刷着刷着，乐趣就上来了。
