Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/645.html
645. Set Mismatch (Easy)
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.
Solution 1. unordered_map
// OJ: https://leetcode.com/problems/set-mismatch
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
unordered_map<int, int> m;
for (auto n : nums) m[n]++;
int missing, dup;
for (int i = 1; i <= nums.size(); ++i) {
if (!m[i]) missing = i;
if (m[i] == 2) dup = i;
}
return { dup, missing };
}
};
Solution 2. Sort
// OJ: https://leetcode.com/problems/set-mismatch/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
sort(nums.begin(), nums.end());
int dup, missing = 1;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] == nums[i - 1]) dup = nums[i];
else if (nums[i] > nums[i - 1] + 1) missing = nums[i - 1] + 1;
}
return { dup, nums.back() != nums.size() ? nums.size() : missing };
}
};
Solution 3. Extra Counts Array
Same idea as Solution 1, but Solution 1 actually requires 2N space, while this approach requires N space.
// OJ: https://leetcode.com/problems/set-mismatch/solution/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> cnts(nums.size(), 0);
int dup, missing;
for (int n : nums) cnts[n - 1]++;
for (int i = 0; i < cnts.size(); ++i) {
if (cnts[i] == 0) missing = i + 1;
else if (cnts[i] == 2) dup = i + 1;
}
return { dup, missing };
}
};
Solution 4. Using Constant Space
If we can encode the Counts Array into nums, we can save space.
When we visit a number n in nums, we invert nums[abs(n) - 1]. If the number n just appears once, the corresponding nums[abs(n) - 1] will be negative. When we see a negative nums[abs(n) - 1], it means n has been visited – it’s the duplicate.
If nums[i] is left positive, then i + 1 is the missing number.
// OJ: https://leetcode.com/problems/set-mismatch/
// Time: O(N)
// Space: O(1)
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int dup, missing;
for (int n : nums) {
if (nums[abs(n) - 1] < 0) dup = abs(n);
else nums[abs(n) - 1] *= -1;
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0) missing = i + 1;
}
return { dup, missing };
}
};
-
class Solution { public int[] findErrorNums(int[] nums) { Arrays.sort(nums); int length = nums.length; int sum = length * (length + 1) / 2; int actualSum = 0; for (int num : nums) actualSum += num; int mismatch = 0; for (int i = 1; i < length; i++) { if (nums[i] == nums[i - 1]) { mismatch = nums[i]; break; } } int difference = sum - actualSum; int missing = mismatch + difference; int[] ret = {mismatch, missing}; return ret; } } ############ class Solution { public int[] findErrorNums(int[] nums) { int eor = 0; for (int i = 1; i <= nums.length; ++i) { eor ^= (i ^ nums[i - 1]); } int diff = eor & (~eor + 1); int a = 0; for (int i = 1; i <= nums.length; ++i) { if ((nums[i - 1] & diff) == 0) { a ^= nums[i - 1]; } if ((i & diff) == 0) { a ^= i; } } int b = eor ^ a; for (int num : nums) { if (a == num) { return new int[] {a, b}; } } return new int[] {b, a}; } } -
// OJ: https://leetcode.com/problems/set-mismatch // Time: O(N) // Space: O(N) class Solution { public: vector<int> findErrorNums(vector<int>& A) { unordered_map<int, int> m; for (auto n : A) m[n]++; int missing, dup; for (int i = 1; i <= A.size(); ++i) { if (!m.count(i)) missing = i; if (m[i] == 2) dup = i; } return { dup, missing }; } }; -
class Solution: def findErrorNums(self, nums: List[int]) -> List[int]: eor, n = 0, len(nums) for i in range(1, n + 1): eor ^= i ^ nums[i - 1] diff = eor & (~eor + 1) a = 0 for i in range(1, n + 1): if (nums[i - 1] & diff) == 0: a ^= nums[i - 1] if (i & diff) == 0: a ^= i b = eor ^ a for num in nums: if a == num: return [a, b] return [b, a] ############ class Solution(object): def findErrorNums(self, nums): """ :type nums: List[int] :rtype: List[int] """ ans = [-1, -1] diff = diffSquare = 0 for i, num in enumerate(nums): diff += i + 1 - num diffSquare += (i + 1) ** 2 - num ** 2 ans[1] = (diffSquare / diff + diff) / 2 ans[0] = ans[1] - diff ans.sort() if diff > 0: return ans return ans[::-1] -
func findErrorNums(nums []int) []int { n := len(nums) for i := 0; i < n; i++ { for nums[i] != i+1 && nums[nums[i]-1] != nums[i] { nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] } } for i := 0; i < n; i++ { if nums[i] != i+1 { return []int{nums[i], i + 1} } } return []int{-1, -1} } -
function findErrorNums(nums: number[]): number[] { let xor = 0; for (let i = 0; i < nums.length; ++i) { xor ^= (i + 1) ^ nums[i]; } let divide = 1; while ((xor & divide) == 0) { divide <<= 1; } let ans1 = 0, ans2 = 0; for (let i = 0; i < nums.length; ++i) { let cur = nums[i]; if (divide & cur) { ans1 ^= cur; } else { ans2 ^= cur; } let idx = i + 1; if (divide & idx) { ans1 ^= idx; } else { ans2 ^= idx; } } return nums.includes(ans1) ? [ans1, ans2] : [ans2, ans1]; }