最近在复习算法和数据结构(基于Python实现),然后看了Python的各种“序列”——比如列表List、元组Tuple和字符串String,后期会写一篇博客介绍 数组
这一数据结构。
不过我们先来看《剑指Offer》中关于数组的一道面试题。
题目一:找出数组中重复的数字 给定一个长度为 n 的数组里的所有数字都在 0∼n−1 的范围内。 数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。 请找出数组中任意一个重复的数字。 样例: 给定 nums = [2, 3, 1, 0, 2, 5, 3] 返回 2 或 3
首先我们得明白,题目要求是 返回任意一个重复的数字
。并没有限定其他条件(时间复杂度和空间复杂度多少),所以解题思路有很多,我们着重看下面这几中解法:
大小的哈希表为代价,看能不能找到
的算法。
以下代码都是用Python实现
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 -- 两数之和解法思路很像,都是对数组中知识的考察。有兴趣的同学可以去做做那道题,代码实现上也很一致。