1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 3 题] “数组中重复的数字”做题记录

[剑指 Offer 第 2 版第 3 题] “数组中重复的数字”做题记录

第 3 题:数组中重复的数字(桶排序,抽屉原理)

传送门:AcWing:数组中重复的数字牛客网 online judge 地址

给定一个长度为 n 的整数数组 nums,数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意:如果某些数字不在 0∼n−1 的范围内,或数组中不包含重复数字,则返回 -1

样例:

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]

返回 23

思路1:最容易想到用哈希表判重。在 n 不超过 32 的时候,使用位运算可以实现 O(1) 空间复杂度判重。

思路2:排序以后,再遍历一遍就知道哪个重复了。

思路3:“抽屉原理”。这道题实际上是要求我们使用桶排序的思想(一个萝卜一个坑),找出重复的数字。

Python 代码:这个解法会修改原始数组

  class Solution(object):
        def duplicateInArray(self, nums):
            """
            :type nums: List[int]
            :rtype int
            """

            size = len(nums)
            if size < 2:
                return -1

            # 先统一检查数字是不是越界了
            for i in range(size):
                if nums[i] < 0 or nums[i] > size - 1:
                    return -1

            for i in range(size):

                # nums[i] 应该在 i 的位置上
                while i != nums[i]:
                    # 发现要交换的那个数和自己一样,就可以返回了
                    if nums[i] == nums[nums[i]]:
                        return nums[i]
                    self.__swap(nums, i, nums[i])
            return -1

        def __swap(self, nums, index1, index2):
            if index1 == index2:
                return
            temp = nums[index1]
            nums[index1] = nums[index2]
            nums[index2] = temp

思路4:下面的问题可以不修改数组找出重复的数字,即使用“二分法”。

LeetCode 第 287 题:寻找重复数

传送门:287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例 1:

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

示例 2:

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

说明:

  1. 不能更改原数组(假设数组是只读的)。
  2. 只能使用额外的 O(1) 的空间。
  3. 时间复杂度小于 O(n^2)
  4. 数组中只有一个重复的数字,但它可能不止重复出现一次。

思路:分治法,用二分去做,是对“数”做二分,而不是对“索引”做二分。

Python 代码:使用了二分法的模板,要定位的“数”根据题意在 1n 之间

  class Solution:

        def findDuplicate(self, nums):
            """
            【不修改数组找出重复的数字】
            给定一个包含 n + 1 个整数的数组 nums,
            其数字都在 1 到 n 之间(包括 1 和 n),
            可知至少存在一个重复的整数。
            假设只有一个重复的整数,找出这个重复的数。
            :type nums: List[int]
            :rtype: int
            """
            left = 1
            right = len(nums) - 1
            while left < right:
                # 取中点有两种方式,偏左和偏右
                mid = left + (right - left + 1) // 2  # 4
                count = 0
                for num in nums:
                    if num < mid:
                        count += 1
                if count < mid:
                    # 比 4 小的个数,最多就只能是 3
                    # 所以重复的肯定不是 [1,2,3],不能排除 4
                    # 因为左边不变,所以取中点的时候,就要偏右
                    left = mid
                else:
                    # 比 4 小的个数,达到 4 或者更多
                    # 重复的就落在 [1,2,3]
                    right = mid - 1
            # 跳出循环肯定是因为 start = end
            return left

参考资料:《剑指 Offer》(第 2 版)第 3 题:数组中重复的数字

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 3 题] “数组中重复的数字”做题记录

链接:https://www.javajike.com/article/3252.html

« [剑指 Offer 第 2 版第 64 题] “求1+2+3+…+n”做题记录
[剑指 Offer 第 2 版第 4 题] “二维数组中的查找”做题记录»

相关推荐

QR code