不修改数组找出重复的数字

#### 题目
给定一个长度为 n+1的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
**数据范围：** 1<=n<=1000

**样例:**
`给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。返回 2 或 3。`

**思考:** 如果只能使用 O(1)的额外空间，该怎么做呢？

#### 解法：

```
class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        # 根据数组nums得到n的值
        length = len(nums)
        n = length - 1

# 对所有约束条件进行限定
        if n < 1:           # 要求n>=1
            return -1

for num in nums:    # 要求数组中的数再1~n之间
            if num < 1 or num > n:
                return -1

# 利用集合记录出现过的数
        seen = set()
        # 如果有重复数字，输出，此算法只输出第一个重复的数
        for num in nums:
            if num in seen:
                return num
            seen.add(num)

nums = [2,3,5,4,3,2,6,7]
result = Solution.duplicateInArray(self='',nums=nums)
print(result)
```
#### 思考解析：利用二分法思想来解决问题
设l=1，r=len（nums），mid=(l+r)>>1
统计数组中的数在[ l , mid ]之间的数目记为s。如果s大于区间长度，则肯定有重复数字出现，则更新r=mid，缩小范围；若不满足，则更新l=mid+1，在另一侧搜索。
**（注意本题的前提条件，即数组中的数在1~length-1之间，否则不能这么写）**
算法：

```
class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 1  # 左边界，假设数字范围从 1 到 len(nums)-1
        r = len(nums) - 1  # 右边界
        while l < r:
            mid = l + r >> 1  # 计算中间值，利用位运算代替除法

# 统计 nums 数组中，值在 [l, mid] 区间内的数字个数
            s = 0
            for i in nums:
                if l <= i <= mid:
                    s += 1

# 如果区间 [l, mid] 内的数字个数大于区间长度（即 mid - l + 1），
            # 说明重复的数字必定在这个区间内，更新右边界 r
            if s > mid - l + 1:
                r = mid
            else:
                l = mid + 1
        return l  # 最终返回重复数字

nums = [2,3,5,4,3,2,6,7]
result = Solution.duplicateInArray(self='',nums=nums)
print(result)
```