题解 | #数组中重复的数字#
数组中重复的数字
http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
法一:利用字典键的唯一性(哈希方法)。
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param numbers int整型一维数组
# @return int整型
#
class Solution:
def duplicate(self , numbers: List[int]) -> int:
mydict={}
for i in numbers:
if i not in mydict:# 字典的键是唯一的。字典中的in 操作符用于判断键是否存在于字典中
mydict[i]=i
else:
return i
return -1
法二:做交换。遍历1-n,While循环直至numbers[i]对应数字i(也就是保证位置不对的一定对应上)。循环过程中判断numbers[i]和numbers[i]为下标的数字数值(即numbers[numbers[i]])是否相等。如果相等,说明该数字重复出现,可以返回;如果不相等,交换二者位置,将numbers[i]放到下标为numbers[i]的位置。(参考题解区牛客330195738号)
class Solution:
def duplicate(self , numbers: List[int]) -> int:
for i in range(len(numbers)):
while i!=numbers[i]:
if numbers[i]==numbers[numbers[i]]:
return numbers[i]
else:
numbers[numbers[i]],numbers[i]=numbers[i],numbers[numbers[i]]
return -1
举例:[3,4,1,2,0,0]
i=0时,i!=numbers[i],numbers更新为[2,4,1,3,0,0];i!=numbers[i],numbers更新为[1,4,2,3,0,0];i!=numbers[i],numbers更新为[4,1,2,3,0,0];i!=numbers[i],numbers更新为[0,1,2,3,4,0]。
i=1,2,3,4时,i==numbers[i],不会进入到while语句里面。
i=5时,i!=numbers[i],而numbers[i]==numbers[numbers[i]],返回numbers[i]。 翻译为:5不等于0,但是0等于0了,因此返回0。
注:如果只是像题解区高赞那样:"遍历数组时,每次检查数字与下标是不是一致的,一致的说明它在属于它的位置上,不一致我们就将其交换到该数字作为下标的位置上。如果交换过程中,那个位置已经出现了等于它下标的数字,那肯定就重复了。"这个方法还是可能检查不出来重复值。
同样举例:[3,4,1,2,0,0]
下标走到numbers[0],第一次交换后,numbers更新为[2,4,1,3,0,0],此时3就位;
下标走到numbers[1],第二次交换后:numbers更新为[2,0,1,3,4,0],此时3,4就位;
下标走到numbers[2],第三次交换后:numbers更新为[2,1,0,3,4,0],此时1,3,4就位;
下标走到numbers[3],第四次交换后:numbers更新为[2,1,0,3,4,0],此时1,3,4就位;
下标走到numbers[4],第五次交换后:numbers更新为[2,1,0,3,4,0],此时1,3,4就位;
下标走到numbers[5],第六次交换后:numbers更新为[0,1,0,3,4,2],此时0,1,3,4就位;
遍历结束。并没有检查出重复的0。