LeetCode 448：找出数组中消失的数字

LeetCode448给你一个含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]Python解法哈希class Solution: def findDisappearedNumbers(self, nums: List[int]) - List[int]: res [] num_set set(nums) for i in range(1, len(nums) 1): if i not in num_set: res.append(i) return res原地修改class Solution: def findDisappearedNumbers(self, nums: List[int]) - List[int]: res [] for num in nums: idx abs(num) - 1 if nums[idx] 0: nums[idx] -nums[idx] for i in range(len(nums)): if nums[i] 0: res.append(i 1) return res原理前提映射数组长 n元素都是 1~n数字x唯一对应下标abs(x)-1。标记规则用数字正负做记号把出现过的数字对应的下标位置翻成负数。提取答案遍历数组仍为正数的下标ii1就是缺失数字。空间特性只改原数组符号不新建容器额外空间 O (1)。Java解法哈希class Solution { public ListInteger findDisappearedNumbers(int[] nums) { ListInteger res new ArrayList(); SetInteger numSet new HashSet(); int n nums.length; for (int x : nums) { numSet.add(x); } for (int i 1; i n; i) { if (!numSet.contains(i)) { res.add(i); } } return res; } }原地修改class Solution { public ListInteger findDisappearedNumbers(int[] nums) { ListInteger res new ArrayList(); int n nums.length; for (int num : nums) { int idx Math.abs(num) - 1; if (nums[idx] 0) { nums[idx] -nums[idx]; } } for (int i 0; i n; i) { if (nums[i] 0) { res.add(i 1); } } return res; } }C解法哈希class Solution { public: vectorint findDisappearedNumbers(vectorint nums) { vectorint res; unordered_setint st(nums.begin(), nums.end()); int n nums.size(); for (int i 1; i n; i) { if (!st.count(i)) { res.push_back(i); } } return res; } };原地修改class Solution { public: vectorint findDisappearedNumbers(vectorint nums) { vectorint res; int n nums.size(); for (int num : nums) { int idx abs(num) - 1; if (nums[idx] 0) { nums[idx] -nums[idx]; } } for (int i 0; i n; i) { if (nums[i] 0) { res.push_back(i 1); } } return res; } };