剑指Offer之面试题3: 数组中重复的数字

举报
宇宙之一粟 发表于 2022/03/29 00:23:34 2022/03/29
【摘要】 数组中重复的数字最近在复习算法和数据结构(基于Python实现),然后看了Python的各种“序列”——比如列表List、元组Tuple和字符串String,后期会写一篇博客介绍 数组 这一数据结构。不过我们先来看《剑指Offer》中关于数组的一道面试题。 面试题3:数组中重复的数字题目一:找出数组中重复的数字给定一个长度为 n 的数组里的所有数字都在 0∼n−1 的范围内。数组中某些数字...

数组中重复的数字

最近在复习算法和数据结构(基于Python实现),然后看了Python的各种“序列”——比如列表List、元组Tuple和字符串String,后期会写一篇博客介绍 数组 这一数据结构。

不过我们先来看《剑指Offer》中关于数组的一道面试题。

面试题3:数组中重复的数字

题目一:找出数组中重复的数字

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

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

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

样例:

给定 nums = [2, 3, 1, 0, 2, 5, 3]

返回 2 或 3

思路

首先我们得明白,题目要求是 返回任意一个重复的数字 。并没有限定其他条件(时间复杂度和空间复杂度多少),所以解题思路有很多,我们着重看下面这几中解法:

  1. 排序后查找:简单的方法就是先把输入的数组排序,排好序的数组,直接比较相邻的两个数就好,如果存在相邻的数组相等,返回这个数。
  2. 利用哈希表:从头到尾按顺序扫描数组的每个数字,每扫到一个数字的时候,如果还没有这个数字,就把它加入哈希表。如果哈希表表中已经存在了该数字,就找到了一个重复的数字。
  3. 时间换空间:我们观察到,利用哈希表的方法是增加了 $ o(n)$ 大小的哈希表为代价,看能不能找到$ o(1) $的算法。

方法一:排序后查找

def find_double_num(nums): 
    """思路一:把输入的数组排序,从排序数组中找出重复的数字 """ 
    nums_sorted = sorted(nums) 
    length = len(nums_sorted) 
    for i in range(1, length): 
        if nums_sorted[i] == nums_sorted[i - 1]: 
            print("重复数字: ", nums_sorted[i]) 
            return True 
    return False

方法二:利用哈希表

def find_double_num2(nums):
    """思路二:哈希表,从头到尾顺序扫描数组中的每个数字,
    哈希表中没有这个数字就加入哈希表。如果哈希表中存在就找到了一个重复的数字"""
    hash_map = dict()
    for i, val in enumerate(nums):
        if val in hash_map:
            print("重复数字: ", val)
            return True
        hash_map[val] = i
    return False

方法三:时间换空间的方法

def find_double_num3(nums):
    if nums is None and len(nums) <= 0:
        return False
    for i in range(len(nums)):
        while i != nums[i]:
            if nums[i] == nums[nums[i]]:
                print("重复数字: ", nums[i])
                return True
            else:
                tmp = nums[i]
                nums[i] = nums[tmp]
                nums[tmp] = tmp
    return False

测试

nums_test = [2, 3, 1, 0, 2, 5, 3]
print(find_double_num(nums_test))
print(find_double_num2(nums_test))
print(find_double_num3(nums_test))

输出结果:

重复数字: 2 True 
重复数字: 2 True 
重复数字: 2 True

总结

其实,刚看到书的这道题,我就觉得很眼熟。仔细想想,这道题跟LeetCode 01 – 两数之和解法思路很像,都是对数组中知识的考察。有兴趣的同学可以去做做那道题,代码实现上也很一致。大家可以对比着刷一下。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。