Problem
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.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than O(n2).
- There is only one duplicate number in the array, but it could be repeated more than once.
Solution1: Binary Search
Time complexity: O(nlogn)
Space complexity: O(1)
Find the smallest m such that len(nums <= m) > m, which means m is the duplicate number.
In the sorted form [1, 2, …, m1, m2, m + 1, …, n]
There are m+1 numbers <= m
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 8 ms class Solution { public: int findDuplicate(vector<int>& nums) { int l = 1; int r = nums.size(); while (l < r) { int m = (r - l) / 2 + l; int count = 0; // len(nums <= m) for (int num : nums) if (num <= m) ++count; if (count <= m) l = m + 1; else r = m; } return l; } }; |
Solution: Linked list cycle
Convert the problem to find the entry point of the cycle in a linked list.
Take the number in the array as the index of next node.
[1,3,4,2,2]
0->1->3->2->4->2 cycle: 2->4->2
[3,1,3,4,2]
0->3->4->2->3->4->2 cycle 3->4->2->3
Time complexity: O(n)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 4 ms class Solution { public: int findDuplicate(vector<int>& nums) { int slow = 0; int fast = 0; while (true) { slow = nums[slow]; fast = nums[nums[fast]]; if (slow == fast) break; } fast = 0; while (fast != slow) { slow = nums[slow]; fast = nums[fast]; } return slow; } }; |