leetcode 287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
题解：
1.长度 n + 1 的整数数组
2.数值在1~n
3.至少存在一个重复的整数
4.只有一个数值重复，返回该数
5.不能更改原数组;可能不止重复出现一次
6.额外的 O(1) 空间；时间复杂度小于 O(n^2)
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
解题思路：二分查找
-
如果不限制条件，题目简单解法还是很多的,比如哈希法，二分查找
-
注意这n+1个数的取值在1~n之间，然后有一个或多个相同的重复元素，这样可以直接用数值来比较了
-
直接用到二分查找框架中，左右端设指针相向移动，需要找到二分判定条件
-
判定条件可以根据这n+1个数取值1~n的特点
-
统计双指针中数，如果小于中数的个数比中数大，则在小于中数的那部分[left, mid]有重复元素；相反地，就在[mid+1, right]那部分
-
直到左右指针相向移动到相同位置，即寻找元素
C/C++题解：
class Solution {
public int findDuplicate(int[] nums) {
int len = nums.size();
int left = 1;
int right = len - 1;
while (left < right) { //直接拿值作比较
int mid = (left + right)/2;
int cnt = 0;
for (int num : nums) { //统计小于中值的个数
if (num <= mid) {
cnt += 1;}}
if (cnt > mid) {// 如果小于中值的个数比中值大
right = mid;// 重复元素位于区间 [left, mid]
} else {// 否则重复元素位于区间[mid + 1, right]
left = mid + 1;}}
return left; }} //最后左右指针共同指向重复元素
Debug结果：
Java题解：
class Solution {
public int findDuplicate(int[] nums) {
int len = nums.length;
int left = 1;
int right = len - 1;
while (left < right) { //直接拿值作比较
int mid = (left + right)/2;
int cnt = 0;
for (int num : nums) { //统计小于中值的个数
if (num <= mid) {
cnt += 1;}}
if (cnt > mid) {// 如果小于中值的个数比中值大
right = mid;// 重复元素位于区间 [left, mid]
} else {// 否则重复元素位于区间[mid + 1, right]
left = mid + 1;}}
return left; }} //最后左右指针共同指向重复元素
Debug结果：
Python题解：
class Solution(object):
def findDuplicate(self, nums):
""" :type nums: List[int] :rtype: int"""
# 数值从1~n,外加一个或多个范围内相同整数=n+1个
n = len(nums)
left = 1
right = n - 1
while left < right: #直接拿值作比较
mid = (left + right)/2
cnt = 0
for num in nums: #统计小于中值的个数
if num <= mid:
cnt += 1
if cnt > mid: # 如果小于中值的个数比中值大
right = mid# 重复元素位于区间 [left, mid]
else: #否则重复元素位于区间[mid + 1, right]
left = mid + 1
return left#最后左右指针共同指向重复元素
Debug结果：
更多题解移步公众号免费获取