男女做那事视频免费网站创立网站

男女做那事视频免费网站,创立网站,嘉兴网站建设有前途吗,网站建设免费书文章目录摘要描述题解答案#xff08;直觉方法#xff09;题解代码#xff08;Swift 可运行 Demo#xff09;题解代码分析为什么要用“负数标记”#xff1f;为什么需要用 abs(nums[i])#xff1f;第二轮遍历为什么能找到缺失值#xff1f;示例测试及结果示例 1示例 2时…文章目录摘要描述题解答案直觉方法题解代码Swift 可运行 Demo题解代码分析为什么要用“负数标记”为什么需要用 abs(nums[i])第二轮遍历为什么能找到缺失值示例测试及结果示例 1示例 2时间复杂度O(n)空间复杂度O(1) 额外空间总结“用符号正负作为额外标记信息”的技巧摘要这题可以说是数组题里最典型的“原地标记法”应用之一。题目要求我们找出1...n中没出现过的数字而且还给了个进阶要求在 O(n) 时间、O(1) 额外空间内完成。听起来好像有点限制但只要利用“数组本身可作为标记空间”的特性就能用非常干净利落的方式解决。这类技巧专项训练非常重要因为真实开发中有很多场景都可以借鉴这种思路。描述输入是一个长度为n的数组里面的每个数字都在[1, n]区间内。我们要返回所有没有出现在数组里的数字。比如nums [4,3,2,7,8,2,3,1] 缺失的是5 和 6或者nums [1,1] 缺失的是2进阶要求我们不能使用额外空间返回结果除外也就是说不能随便用哈希表、map 之类的辅助结构。题解答案直觉方法利用这样一个事实数组中的值都在[1, n]范围内那么每个值x对应数组位置x-1必定存在。我们可以利用“把出现过的数字对应的位置标记为负数”这种方式把数组本身变成一个“出现记录表”。整体思路遍历数组对于每个数字x我们让数组中x-1的位置变成负数如果还没负遍历标记后的数组所有仍然是正数的位置i说明数字i1没出现过这是典型的“使用符号作为标记”的技巧。题解代码Swift 可运行 DemoimportFoundationclassSolution{funcfindDisappearedNumbers(_nums:[Int])-[Int]{varnumsnums// 复制一份便于原地修改letnnums.count// 第一步把出现过的数字对应位置标记成负数foriin0..n{letindexabs(nums[i])-1ifnums[index]0{nums[index]-nums[index]}}// 第二步正数的位置就是缺失的数字varresult[Int]()foriin0..n{ifnums[i]0{result.append(i1)}}returnresult}}// MARK: - DemoletsolutionSolution()print(示例 1,solution.findDisappearedNumbers([4,3,2,7,8,2,3,1]))// [5, 6]print(示例 2,solution.findDisappearedNumbers([1,1]))// [2]题解代码分析为什么要用“负数标记”这是这题最精妙的地方。数组长度为 n所有数字范围都在1...n那么数字和索引之间刚好可以一一映射。例子数字 4 —— 对应索引 3 数字 1 —— 对应索引 0 数字 7 —— 对应索引 6利用这点我们可以把“某个数字出现过”这件事记录到nums[x-1]中。最简单的标记方式就是→把 nums[x-1] 变成负数负数代表“已经被访问过了”。为什么不直接改成 0 或者某个标志值因为之后我们仍然需要判断原本的值而负数保留了数值本身的信息且不会和[1,n]冲突。为什么需要用abs(nums[i])因为标记过程中有些位置已经变成负数了所以必须取绝对值。第二轮遍历为什么能找到缺失值因为出现过的数字对应位置已经被标记为负数没出现过的位置仍然是正数所以第 i 个位置是正数 → i 1 没出现过就是缺失值。示例测试及结果我们用题目给的例子跑一下示例 1输入 [4,3,2,7,8,2,3,1] 中间标记过程如下 原始 4 3 2 7 8 2 3 1 标记后 -4 -3 -2 -7 8 -2 -3 -1 ↑ ↑ 正 正 缺失数字为[5, 6]示例 2输入 [1,1] 标记后[-1, 1] 缺失的是 2运行 Demo 即可得到相同结果。时间复杂度O(n)一次遍历标记出现过的数字一次遍历找出没被标记的位置两次线性扫描总共 O(n)在大数据量下仍然非常稳定。空间复杂度O(1) 额外空间注意返回的结果数组不算额外空间。其余操作都在原数组上原地完成不需要新开结构。总结这题真正想让你掌握的是“用符号正负作为额外标记信息”的技巧它在很多 O(1) 空间的题里都能出现比如找重复数字找缺失数字数组原地哈希原地 bucket 标记在实际业务逻辑中这种技巧也能用于用户状态表中“是否访问过”的标记即使在共享数据结构中工具链中处理序列时进行轻量级标记内存敏感场景的原地修改技巧