LeetCode 448. 找到所有数组中消失的数字
题目介绍：
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例：
输入： nums = [4,3,2,7,8,2,3,1,2,1] 输出： [5,6, 9, 10]
方案一：利用数组的includes方法
遍历1-n之间的所有数，判断当前数是否已经在数组nums中了，不存在的放在数组中返回即可~
小课堂：
includes()方法可以判断元素是否在数组中，如果在返回true，否则返回false。
Up Code ~ 上码~
/** * @method findDisappearedNumbers1 * @description: 利用数组的includes方法 * @param {number} nums * @return {*} */ function findDisappearedNumbers1(nums: number[]): number[] { // 获取数组长度 const n = nums.length; // 定义存放结果的数组 const res: number[] = []; // 遍历1-n之间的每一个元素 for (let i = 1; i <= n; i++) { // 如果nums中不存在i，直接放入结果中 if (!nums.includes(i)) { res.push(i); } } // 返回结果 return res; }
算法复杂度：
- 空间复杂度：定义的
res存放结果，最大O(n)O(n)O(n)
- 时间复杂度：外层是
for循环 O(n)O(n)O(n)，内部有includes方法
O(n)O(n)O(n)，整体时间复杂度是O(n2)O(n^2)O(n2)
时间复杂度是O(n2)O(n^2)O(n2)肯定不是我们想要的~
方案二：两次循环，特殊标记
我们可以生成一个指定nums.length长度的数组arr，在遍历nums元素时，如果某个i值出现了，则在arr中相应的索引位置打标记为true，最后我们筛选arr中标记不为true的值即可。
/** * @method findDisappearedNumbers2 * @description: 两次循环，特殊标记 * @param {number} nums * @return {*} */ function findDisappearedNumbers2(nums: number[]): number[] { // 1. 生成指定长度的索引 const arr = new Array(nums.length); // 2. 遍历nums中的每一个值 for (let i = 0; i < nums.length; i++) { // 对应arr中的索引是从0开始的，所以这个位置的索引位置 - 1 arr[nums[i] - 1] = true; } // 定义存放结果的数组 let res = []; // 3. 遍历arr中所有的元素 for (let i = 0; i < arr.length; i++) { // 如果当前项不是true，表示没有存在过 if (arr[i] !== true) { // 注意这里的索引i，是从0开始的，所以对应位置要+1 res.push(i + 1); } } // 返回结果 return res; }
算法复杂度：
- 空间复杂度：定义的
res存放结果，最大O(n)O(n)O(n)
- 时间复杂度：两次循环，量级是O(n)O(n)O(n)
性能对比
用事实说话，那种方案更好一些~
const nums: number[] = [4, 3, 2, 7, 8, 2, 3, 1]; console.time('findDisappearedNumbers1'); for (let i = 0; i < 200 * 10000; i++) { findDisappearedNumbers1(nums); } console.timeEnd('findDisappearedNumbers1'); console.time('findDisappearedNumbers2'); for (let i = 0; i < 200 * 10000; i++) { findDisappearedNumbers2(nums); } console.timeEnd('findDisappearedNumbers2');
网络异常，图片无法展示
|
二者对比，方案二更优秀~
