- We need
binary searchbut apparently, we cannot do that on
numsbecause it’s not sorted.
- By the definition, the range
[1, n]can be the target of binary search.
middle, then iterate through
nums, and record num that are
countis strictly bigger than
middle, it means there must be more than
[1, middle]. So the repetitve num must be inside. So, move
right = middle.
count <= middle, we can say there is def no repetitve num between
[1, middle]. Move
left = middle + 1.
Given an array of integers
n + 1 integers where each integer is in the range
[1, n] inclusive.
There is only one repeated number in
nums, return this repeated number.
You must solve the problem without modifying the array
nums and uses only constant extra space.
Input: nums = [1,3,4,2,2]