Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Submit your solution: https://leetcode.com/problems/find-the-duplicate-number/
Sorting O(nlogn)
If we sort the numbers (the complexity is O(nlogn)), we can just check (O(n)) from the start to the end for any two neighbouring numbers.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: int findDuplicate(vector<int>& nums) { sort(nums.begin(), nums.end()); for (int i = 1; i < nums.size(); i ++) { if (nums[i] == nums[i - 1]) { return nums[i]; } } return 0; } }; |
class Solution {
public:
int findDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i ++) {
if (nums[i] == nums[i - 1]) {
return nums[i];
}
}
return 0;
}
};This method modifies the original array.
Using Hash/Set
If we remember the number when they first appear, we can use hash/set to check if it is a duplicate. This method does not fully use the number are within 1 to n (inclusive).
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: int findDuplicate(vector<int>& nums) { unordered_set<int> cache; for (int i = 0; i < nums.size(); i ++) { if (cache.count(nums[i])) { return nums[i]; } cache.insert(nums[i]); } return 0; // for complier } }; |
class Solution {
public:
int findDuplicate(vector<int>& nums) {
unordered_set<int> cache;
for (int i = 0; i < nums.size(); i ++) {
if (cache.count(nums[i])) {
return nums[i];
}
cache.insert(nums[i]);
}
return 0; // for complier
}
};O(n) time complexity but O(n) space complexity as well using Hash/Set.
Binary Search
Since the input numbers are within the range of 1 to n inclusive, if we pick a number and count how many numbers are smaller than it, if it is bigger than the number, meaning there is a duplicate below it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: int findDuplicate(vector<int>& nums) { int high = nums.size() - 1; int low = 1; while (low <= high) { int mid = low + (high - low) / 2; int c = 0; for (int a: nums) { if (a <= mid) { ++ c; } } if (c <= mid) { low = mid + 1; } else { high = mid - 1; } } return low; } }; |
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int high = nums.size() - 1;
int low = 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int c = 0;
for (int a: nums) {
if (a <= mid) {
++ c;
}
}
if (c <= mid) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
};Binary search is O(logn) and the counting has O(n) complexity, therefore the method has O(nlogn) time complexity. It does not modify the array and the space complexity is O(1).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: C++ Coding Exercise - Binary Tree Postorder Traversal
Next Post: Compute the Maximum Subarray via Dynamic Programming or Greedy Algorithms
There is an O(1) space and O(n) runtime solution. XOR all numbers from 1 to n (inclusive) and XOR all numbers in the array. XOR both and you get the duplicate.
Input [2,2,2,2,2]
2 XOR 2 XOR 2 XOR 2 XOR 2 = 2
1 XOR 2 XOR 3 XOR 4 = 4
2 XOR 4 = 6
Do not discard your own assumption: “Assume that there is only one duplicate number, find the duplicate one”.
I now understand your solution, however, according to https://leetcode.com/problems/find-the-duplicate-number/ it has only one duplicate number, but the duplicate number may appear multiple times.
int findDuplicate(vector& nums) {
int x = 0;
for (int i = 0; i < nums.size(); i ++) { x ^= nums[i]; } int y = 0; for (int i = 0; i <= nums.size() - 1; i ++) { y ^= i; } return x ^ y; }