剑指offer 面试题3 python版+解析: 数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

如果用循环扫描的话，面试官会不满意，所以采取空间复杂度为O(1)的算法：

数组中的数字都在0~n-1的范围内，如果这个数组中没有重复的数字，则排序后数字i将出现在下标为i的位置。若有重复数字，则有的位置存在多个数字，有的位置没有数字。所以，

1. 我们从头到尾扫描这个数字，当扫描到下标为i的数字时，首先比较这个数字是不是为i，如果是就扫描下一个数字，如果不是就拿它和第m个数字进行比较。

2. 如果它和第m个数字相等，就找到了一个重复数字，如果它和m不相等，就交换位置。

3. 重复这个操作直到发现重复的数字。

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        length = len(numbers)
        for i in range(length):
            while numbers[i]!= i:
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                else:
                    tmp = numbers[numbers[i]]
                    numbers[numbers[i]] = numbers[i]
                    numbers[i] = tmp
        return False

如果要求不改变原来的数组，则采用二分法加统计区间数字的方法。把1~n的数字从中间的数字m分为两部分，前面一部分为1~m，后面一部分为m+1~n，如果1~m的数字数目超过m，则包含重复数字，另一部分同理。然后继续把包含重复数字的区间一分为二，直到找到一个重复的数字。

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        length = len(numbers)
        start = 1
        end = length - 1
        while(end>=start):
            mid = int((end - start)/2 + start)
            count = self.CountNumber(numbers, start, mid, length)
            if (end == start):
                if (count>1):
                    duplication[0]= start
                    return True
                else:
                    break
            if (count>(mid-start+1)):
                end = mid
            else:
                start = mid+1
        return False
                
    def CountNumber(self, numbers, start, end, length):
        count = 0
        for i in range(length):
            if (numbers[i]>=start and numbers[i]<=end):
                count = count+1
        return count