塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-3数组中重复的数字-python

《剑指offer》python实现系列,全目录

最简单的方法是遍历数组,
优化:创建一个长度为n的辅助数组temp,读取原数组值x,令temp[x]=1,再读入新元素检测是否为1即可。

使用辅助数组
1
2
3
4
5
6
7
8
9
def duplicate( numbers, duplication):
temp = [0]*len(numbers)

for i in numbers:
if temp[i] == 1:
duplication[0] = i
return True
temp[i] = 1
return False

不使用辅助数组:
直接在原数组上交换元素,确保元素与其下标相等。
详细思路:看书上的例子p39

1
2
3
4
5
6
7
8
9
def duplicate( numbers, duplication):
for i in range(0,len(numbers)):
while i != numbers[i]:#保证元素与下标i对应
if numbers[numbers[i]] == numbers[i]: #如果已经有元素
duplication[0] = numbers[i]
return True
else:
numbers[numbers[i]], numbers[i] = numbers[i], numbers[numbers[i]] #交换位置
return False
if help:小手一抖点个广告 or 大手一挥资助一下