四种方法，不同角度解释
数组中重复的数字
http://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
#方法一 排序后再遍历 时间O(n*logn) 空间O(1)
if (not numbers)&nbs***bsp;len(numbers) == 1:
return False
numbers.sort()
temp = numbers[0]
for i in range(1,len(numbers)):
if temp == numbers[i]:
duplication[0] = temp
return True
temp = numbers[i]
return False
#方法二 使用哈希表 时间O(1) 空间O(n)
dic = {}
for i in numbers:
if i in dic and dic[i] == 1:
duplication[0] = i
return True
dic[i] = 1
return False
#方法三 下标定位法 时间O(n) 空间O(1)
for i in range(len(numbers)):
while i != numbers[i]:
if numbers[i] == numbers[numbers[i]]:
duplication[0] = numbers[i]
return True
temp = numbers[i]
numbers[i] = numbers[temp]
numbers[temp] = temp
return False
# 方法四 使用内置函数
import collections
if len(numbers) == len(set(numbers)):
return False
duplication[0] = collections.Counter(numbers).most_common(1)[0][0]
return True
