[python3] 3_02 不修改数组找出重复的数字

题目如下

题目

思路1

类似于面试题3_01中的思路3，只不过修改数组顺序的过程在辅助数组进行。创建一个长度为n+1的辅助数组，将元素组的元素i复制到辅助数组下标为i的位置。

思路2

借助二分查找算法。

二分查找算法：二分查找也称折半查找，它要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
具体算法步骤：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。（ps：这里的关键字指的是数组元素）

数组是顺序存储结构，因此本题借助一个有序的数组[1, 2, 3, 4, 5, ... n+1]来完成题目要求。首先，构造一个待不断二分的数组为numbers = [1, 2, 3, 4, 5, ... n+1]，记为numbers = [start, ...., end]。先寻找表中间位置的数组元素middle，根据该数组元素middle将数组分为两个字表a和b，在输入数组(即题目中要求不可修改的数组)中查找每个字表内数字出现的个数，若个数大于当前字表的长度，说明当前字表内存在重复数字。将当前字表继续一分为二，重复上述过程，直到出现重复数字为止。

代码如下

# 03_02_FindDuplicationNoEdit.py
class Solution(object):
    def getDuplication(self, numbers, length):
        if numbers == []:
            return 0
        start = 1
        end = length - 1
        while start <= end:
            middle = (end - start) // 2 + start
            print("middle:", middle)
            count = self.countRange(numbers, length, start, middle)
            print("start + end + middle + count:", start, end, middle, count)
            if (end == start):
                if count > 1:
                    return start
            if count > (middle - start + 1):
                end = middle
            else:
                start = middle + 1
    def countRange(self, numbers, length, start, end):
        if numbers == []:
            return 0
        count = 0
        for i in range(0, length - 1):
            if numbers[i] >= start and numbers[i] <= end:
                count = count + 1
        return count

# 正常输入示例
print("---test1---")
numbers1 = [2, 3, 5, 4, 3, 2, 6, 7]
length1 = 8
a = Solution()
aa = a.getDuplication(numbers1, length1)
print(aa)

# 无效输入测试用例（输入空指针）
print("---test2---")
numbers2 = []
length2 = 0
b = Solution()
bb = b.getDuplication(numbers2, length2)
print(bb)

运行结果如下

测试用例运行结果

结果分析

此方法不能找到数组内所有的重复数字。

思路3

类似于面试题3_01中的思路2，采用collections模块的Counter()函数。

新手刷题，若有任何疑问或者问题请留言，欢迎交流~~