LeetCode Set Mismatch
The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:
Input: nums = [1,2,2,4] Output: [2,3]Note:
- The given array size will in the range [2, 10000].
- The given array’s numbers won’t have any order.
一个大小为n的数组，本来包含1~n这n个数，但是某个数x“突变”成y了，这就导致数组中丢了x，而y重复出现了两次，现在要找出丢掉的x和重复的y。 简单题，首先用hash可以找到重复的y，然后根据数学关系可以找到x，本来1~n的和是S=n*(n+1)/2，设现在的和是T，则有x=y-T+S。 代码如下： [cpp] class Solution { public: vector<int> findErrorNums(vector<int>& nums) { vector<int> ans(2, 0); unordered_set<int> hash; int sum = 0, n = nums.size(); for (const auto& num : nums) { if (hash.find(num) != hash.end())ans[0] = num; hash.insert(num); sum += num; } ans[1] = ans[0] – sum + n*(n + 1) / 2; return ans; } }; [/cpp] 本代码提交AC，用时59MS。 还有一种空间复杂度O(1)的方法，不过需要改变原有数组。 因为数组元素是1~n的，所以遍历数组，把数值-1当作下标访问数组，使该处的元素变为原来的相反数，如果遇到某个数y-1访问的那个数是负数，说明y重复了，之前有一个y把y-1处的数变成了负数。 遍历完一遍之后，丢失的那个数x指向的x-1处的数应该是正数，因为x丢掉了，没有经过上面的过程，所以再遍历一遍可以找到x。 整个过程不需要借助额外的空间，代码如下： [cpp] class Solution { public: vector<int> findErrorNums(vector<int>& nums) { vector<int> ans(2, 0); for (int i = 0; i < nums.size(); ++i) { int idx = nums[i] < 0 ? -nums[i] : nums[i]; if (nums[idx – 1] < 0) { ans[0] = idx; } else { nums[idx – 1] = -nums[idx – 1]; } } for (int i = 0; i < nums.size(); ++i) { if (nums[i] > 0) { ans[1] = i + 1; break; } } return ans; } }; [/cpp] 本代码提交AC，用时36MS。]]>