Python语言实现
摘要
从这个时间段开始，做一些编程的练习。回想起来，入学已经一年有余了，一直以来学的东西杂而多，感觉有一些抓不到主要矛盾，不过，大的方向上存在的技术壁垒还是依然存在的，我想，无论以后具体从事的是哪一种岗位，基本功还是需要的，现在想想也是可笑。每天学的东西听起来都是高大上，可以真正自己有几斤几两，还是特别清楚的。所以还是把基础打好吧。另外，在实验室的学习暂时没有项目作为引导，所以实习是很有必要。过了这一段时间，是该要出去锻炼一下了。
1.采用字典（类似hash表）方法
利用字典表结构解决，首先定义一个空字典，然后从头到尾扫描数组中的每个数字，如果发现该数字不在在字典中（最初字典为空，所以第一个数字绝对满足），则将该数字加入到字典作为键，值可任意（如为0），继续查询，若查询到某数字存在于字典中，则证明存在重复，输出到duplication[0]中，返回True,否则返回False.
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
dict = {}
for num in numbers:
if num not in dict:
dict[num]=0
else:
duplication[0]=num
return True
return False
为何不用list代替dict作为缓冲对象，因为dict.keys()实际上是list(keys),是dict的所有key组成的list。查找一个元素是否在list中是以list的下标为索引遍历list.而查询是否在dict中，是将key以hash值的形式直接找到key对应的索引，根据索引可直接访问value。对量大的dict查询，自然是后者快很多。
以上方法可以实现时间复杂度为O(n),空间复杂度为O(n)。
2.空间复杂度为O(1)的解法
注意到数组中的数字都在0~n-1之间，若没有重复，则数组重排序之后数字i将出现在第i个位置，否则，就会出现重复或者位置缺失。做如下重排：依次扫描这个数组中的数字，当扫描到下标为i的数字时，首先比较这个数字（m表示）是不是i,若是，则接着扫描下一个数字；若不是，则用它与第m个数字进行比较，若与第m个数字相同，则找到一个重复的数字。若不相等，就把它与第m个数字交换。把m放到属于它的地方。如此循环。直到发现重复的数字。(该方法会改变数组的值)
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
if numbers is None or len(numbers) == 0:
return False
for i in numbers:
if i < 0 or i >= len(numbers):
return False
for i in range(len(numbers)):
while i != numbers[i]:
if numbers[i] == numbers[numbers[i]]:
duplication[0]=numbers[i]
return True
temp = numbers[numbers[i]]
numbers[numbers[i]]= numbers[i]
numbers[i] = temp
return False
3.利用现有数组为标志位
不需要额外的数组保存，利用题目中说“数组里数字的范围在0 ~ n-1 之间”，所以可以利用现有数组设置标志，当一个数字被访问过后，可以设置对应位上的数 + n，之后再遇到相同的数时，会发现对应位上的数已经大于等于n了，那么直接返回这个数即可。(该方法会改变数组的值)
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
long = len(numbers)
for i in range(len(numbers)):
index = numbers[i]%long if numbers[i] >= long else numbers[i]
if numbers[index] > long:
duplication[0] = index
return True
numbers[index] += long
return False
