寻找重复数(Leetcode 287)

发表于 | 分类于 ， ， ， ， | | 本文总阅读数 次
| 字数统计: 924 | 阅读时长 ≈ 3
Leetcode 287

1

题目分析

   这道题也是找数字的题目，但是不同的是，之前讲的都是在重复数字中找单独出现的数字，而这个题目是在单独的数字中，查找重复数字，又该如何去应对呢？

二分查找

因为题目中数字是从1到n，而且存在重复元素，元素的总个数为n+1。我们思考，如果元素总个数为n，并且无重复元素的情况下，那么不就是从1到n的随机排列吗？那么多了一个数，必然存在重复的情况，假设重复的元素为x，当$k \ge x$时，那么小于等于k的元素个数有k + 1个，当$k < x$时，那么小于等于k的元素有k个。我们思考如果不是从1到n全都存在的情况下，即有一个数字重复出现很多次的情况，这种思路还正确吗？当然也是正确的，小伙伴们可以举个例子验证一下，我也只可意会不可言传。因此可以考虑二分法进行求解。
令k=mid，当mid代入时，数组中小于mid的元素个数大于mid时，说明$mid \ge x$，则令right = mid。否则令left = mid + 1。时间复杂度为O(nlog(n))，空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findDuplicate(self, nums):
        n = len(nums)
        left, right = 1, n - 1
        while left < right:
            mid = (left + right) // 2
            cnt = sum([x <= mid for x in nums])
            if cnt > mid:
                right = mid
            else:
                left = mid + 1
        return left

位运算

这个位运算很简单，从1到n，分别计算每一位上出现的总个数，因为有一个数x重复，假设x的某个二进制位为1，则数组中该位为1的数字个数一定大于从1到n所有数字中该位为1的数字个数，否则一定小于等于。因此我们按位进行比较，最后哪些位为1，就可以得到该数字的二进制表示。时间复杂度为O(nlog(n))，空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findDuplicate(self, nums):
        n = len(nums)
        k = len(bin(n)) - 2
        res = 0
        for i in range(k):
            bit_nums, bit_origin = 0, 0
            for x in nums:
                if x & (1 << i):
                    bit_nums += 1
            for x in range(1, n):
                if x & (1 << i):
                    bit_origin += 1
            if bit_origin < bit_nums:
                res |= 1 << i
        return res

双指针

这题很难想出和双指针有什么关系，官方和一些民间大神总有一些骚想法，我们来看一看。因为数组的长度为n+1，数组的最大值为n，因此我们可以看成数组中每个元素保存的是下一个元素的索引，这样就相当于一个指针。因此有重复的数字，说明构成了环。我们需要找到环的入口处。
这个问题就转化成了一个经典的快慢指针问题。我们以题目中的例子进行讲解。
q
时间复杂度为O(n)，空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findDuplicate(self, nums):
        slow = 0
        fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        find = 0
        while True:
            find = nums[find]
            slow = nums[slow]
            if find == slow:
                return find

刷题总结

  这类题目基本上结束了，无论是从多次出现的数组中寻找单独出现的数字，还是从单独出现的数字中寻找多次出现的数字，都可以使用一些奇技淫巧优化算法。如果面试问到了，掌握最普通的暴力求解法是最最基本的，但是面试官既然出这个题目，一定不是想考察暴力解法，所以小伙伴们一定要掌握呦~

-------------本文结束感谢您的阅读-------------
0%