leetcode回顾——Find the Duplicate Number

LeetCode

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2
示例 2:

输入: [3,1,3,4,2]
输出: 3
说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

解析

题目有一个很关键的信息——长度为n + 1的数组，并且数字都在1～n之间，如果该题目允许我们改变原数组的话，我们只需要对数组进行排序，然后一次遍历即可，但是现在题目要求我们不改变原数组，因此，对原数组排序就行不通了。虽然不允许我们对原数组排序，但是，我们可以这样想，既然这个数组内的元素范围在1～n，但是长度却是n + 1，假设a、b均在这个数组中，当[a, b]中不存在重复数字时，那么，区间[a, b]的长度就等于(a - b + 1),如果存在重复数字，那么区间长度就变成了(a - b + 2)，那么如何计算这个区间长度呢？这个时候就要利用一下排序以及二分的思想，找到[1, n]区间的中间数字m，分为两个区间[1, m], [m + 1, n]，在[1, m]区间中计算大于等于1且小于等于m的元素的个数，如果个数等于(m - 1 + 1)，那么重复数字就落在了[m + 1, n]当中，否则，再次对[1, m]进行二分计算两个子区间的长度，最后找到重复的数字

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        start = 1
        end = len(nums) - 1
        while start <= end:
            mid = start + int((end - start) / 2)
            c = self.count(nums=nums, start=start, end=mid)
            if start == end:
                if c > 1:
                    return start
                else:
                    break
            if c > (mid - start + 1):
                end = mid
            else:
                start = mid + 1
        return -1
    
    def count(self, nums, start, end):
        n = 0
        for i in range(len(nums)):
            if nums[i] >= start and nums[i] <= end:
                n += 1
        return n


if __name__ == '__main__':
    s = Solution()
    t = [1,3,4,2,2]
    print(s.findDuplicate(nums=t))

学习自：https://blog.csdn.net/whdAlive/article/details/80459730