- 题目描述：
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
- 算法思路：
证明一定存在重复元素：
令集合A = {1,2,3,4,...,n}， B = {bi| 1 <= i <= n + 1}，有|A| = n，|B| = n + 1，
将n个数字放入到n + 1个成员的数组可以形式化为函数，f: B -> A，即f(bi) ∈ A，
首先假设映射f是单射，即∀bi， bj∈B， bi ≠ bj ⟹ f(bi) ≠ f(bj)，
即f将B的n + 1个元素映射到A的n + 1个不同的元素上，即f(B) ⊆ A，|f(B)| <= |A|，
又因为|f(B)| = n + 1，|A| = n，有n + 1 <= n矛盾，所以映射f不是单射而是多射，
即一定存在重复元素。
首先思考在不使用常量级额外空间的情况下如何做，显然能想到的第一种方式就是设定一个长度为n的数组cnt，用下标对应1 ~ n的数字，
遍历数组nums，如果nums[i] == j其中i是遍历的下标，j是nums的元素值并且是辅助数组的对应下标 + 1，这样只需要遍历nums一次，记录每个元素的出现次数然后找出大于1的即可，
但题目要求常量空间复杂度，又因为重复数x一定有1 <= x <= n具有有序性，所以可以考虑用二分查找解决问题，难点在于二分逻辑，
假设重复数x，数组中的数要么大于x，要么小于等于x，这里统计小于等于x的元素个数用辅助数组cnt记录，
由于题目规定只有一个重复数，假设重复数x只有两个，另一个占据第n + 1个位置，
那么此时nums中小于等于x的元素个数应该等于x + 1，那么对于之后所有大于x的元素，假设是y而言，小于等于它们的元素个数也就应该是y + 1即cnt[y] > y，
而对于小于x的元素，假设是z，则cnt[z] <= z，
所以对一个数x，如果x > cnt[x]，则x可能是重复数，如果x <= cnt[x]，则x一定不是重复数，这样就得到了二分的逻辑，
如果重复数x的个数超过2，则必然有至少一个数被x替代，假设这个数i < x，对于[i, x - 1]的cnt都减1，依然满足cnt[z] <= z，
如果这个数i > x，对[x + 1, i]的cnt都加1，依然满足cnt[y] > y，
为满足限制额外空间为常量级，可以每次循环记录小于等于数值的元素的个数，这样相当于在二分查找中加入了一次O(n)的遍历，
时间复杂度变为O(n log(n))
- 代码：
时间复杂度：O(n log(n))
int findDuplicate(vector<int>& nums) {int lower_bound = 1, upper_bound = nums.size() - 1;while (lower_bound < upper_bound) {int mid = lower_bound + (upper_bound - lower_bound) / 2;int lower_equal_count = 0;for (const int &n : nums) {if (n <= mid) {++lower_equal_count;}}if (lower_equal_count > mid) {upper_bound = mid;} else {lower_bound = mid + 1;}}return lower_bound;}