每天进步一点点🤏

找到所有数组中消失的数字

  • 645 字

找到所有数组中消失的数字

题目

1
2
3
4
5
6
7
8
9
10
给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内
请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果

示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：
输入：nums = [1,1]
输出：[2]

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
思路:
直接遍历1-n的数组,然后in_array,会导致超时,相当于遍历了n*n次
正确方法是array_flip翻转key和value,查看1-n是否是新数组的下标,相当于遍历n次

代码:
/**
 * @param Integer[] $nums
 *
 * @return Integer[]
 */
function findDisappearedNumbers($nums)
{
    $count = count($nums);
    $nums  = array_flip($nums);

    $arr = [];
    for ($i = 1; $i <= $count; $i++) {
        if (!isset($nums[$i])) {
            $arr[] = $i;
        }
    }

    return $arr;
}