287 Find the Duplicate Number
Last updated
Was this helpful?
Last updated
Was this helpful?
Given an arraynumscontainingn+ 1 integers where each integer is between 1 andn(inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
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 thanO(n^2)
.
There is only one duplicate number in the array, but it could be repeated more than once.
(1) Binary Search
(2) Two Pointers
Binary Search: 时间复杂度O(nlogn), 空间复杂度O(1)
Two Pointers: 时间复杂度O(n), 空间复杂度O(1)