首页 > 试题广场 >

数组中重复的数字

[编程题]数组中重复的数字

热度指数：535558 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

返回描述：

如果数组中有重复的数字，函数返回true，否则返回false。

如果数组中有重复的数字，把重复的数字放到参数duplication[0]中。（ps:duplication已经初始化，可以直接赋值使用。）

算法知识视频讲解

推荐

BoTinker

不需要额外的数组或者hash table来保存，题目里写了数组里数字的范围保证在0 ~ n-1 之间，所以可以利用现有数组设置标志，当一个数字被访问过后，可以设置对应位上的数 + n，之后再遇到相同的数时，会发现对应位上的数已经大于等于n了，那么直接返回这个数即可。

代码是C：

int find_dup( int numbers[], int length) {

for ( int i= 0 ; i<length; i++) {

int index = numbers[i];

if (index >= length) {

index -= length;

}

if (numbers[index] >= length) {

return index;

}

numbers[index] = numbers[index] + length;

}

return - 1 ;

}

不需要额外的空间消耗，时间效率是O(n)

编辑于 2015-06-19 16:59:45 回复(97)

Python

牛客860134730号

可以先将列表元素排序，然后numbers【i】和numbers【i+1】进行比较，如果相等，说明有元素一样，停止循环，然后赋值即可。

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]   #注意条件
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        temp = [None]             #需要一个临时存储
        numbers.sort()
        for i in range(len(numbers)-1):
            if numbers[i] == numbers[i+1]:
                temp[0] = numbers[i]
                break 
        if temp[0] != None:
            duplication[0] = temp[0]   #这是条件
            return True
        else:
            return False

发表于 2020-09-30 12:01:18 回复(0)

Python

BJ-2020

思路：
1.a[i] 与 i 比较：
==：也就是一个萝卜一个坑，构成递增数列
!=：继续比较：
a[i]与a[a[i]]
== 肯定重复了一个萝卜一个坑，这里出现了一个萝卜出现在了两个坑里
!= 交换坑里的萝卜

矛盾点：
如果 a[i] != i
那么 a[i] != a[a[i]]
但是一旦相等，那就出现了矛盾

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if numbers == None:
            return False
        for i in range(len(numbers)):
            if numbers[i]  len(numbers)- 1:
                return False
        for i in range(len(numbers)):
            while numbers[i] != i:
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                else:
                    temp = numbers[i]
                    numbers[i],numbers[temp] = numbers[temp], numbers[i]
        return False

发表于 2020-09-06 22:08:59 回复(1)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        import collections
        c = collections.Counter(numbers)
        for k in c:
            if c[k] > 1:
                duplication[0] = k
                return True
        return False

1，在这个题上花了很多时间时因为我以为要按照题意返回重复的第一个数的数值，所以一直报错。

2，后来参考牛友的代码以及看清楚注释：

# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False

改正了代码

发表于 2020-07-27 11:34:44 回复(0)

Python

wayToHappiness

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        length=len(numbers)
        if length<2:
            return False
        i=0
        while i<length:
            while numbers[i]!=i:
                if numbers[i]==numbers[numbers[i]]:
                    duplication[0]=numbers[i]
                    return True
                numbers[numbers[i]],numbers[i]=numbers[i],numbers[numbers[i]]

            i+=1
        return False

比较奇怪的是，交换两个位置的值时，这样写可以通过，反过来就会显示超时

发表于 2020-07-24 21:56:11 回复(0)

Python

清风思月

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        only = [] # 创建一个唯一元素的列表
        for num in numbers:
            if num in only:# 发现第一个重复元素则返回
                duplication[0] = num
                return True
            else:
                only.append(num)
        return False

发表于 2020-07-16 22:06:38 回复(0)

Python

小小测试学编程

这样写是不是狠废？昨天面试官问我的时候，我就这么回了。。。😪😪

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        new_n = list(set(numbers))
        count = 0
        for i in new_n:
            for j in numbers:
                if i == j:
                    count+=1
            if count == 1:
                count = 0
            elif count > 1:
                duplication[0]=i
                return True
        return False
        # write code here

# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        temp_dict = Counter(numbers)
        flag = 0
        for k,v in temp_dict.items():
            if v>1:
                flag = 1
                duplication[0] = k
                return True
        if flag == 0 :return False
        # write code here

编辑于 2020-06-16 16:29:17 回复(0)

Python

一直爬的蜗牛

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        for i in numbers:
            if i not in duplication:
                duplication.append(i)
            else:
                duplication.insert(0,i)
                return True
        else:
            return False

发表于 2020-06-12 22:49:47 回复(1)

Python

Bambam.

代码思路：

exist = [False for _ in range(len(numbers))] # 该数组为长度与numbers相同的初始化数组

for i in numbers:

if exist[i]: #判断数字i是否存在，若已经存在，执行下列代码

duplication[0] = i #将重复数字i存入duplication[0]

return True

exist[i] = True #数字i第一次出现，改变初始数组中的状态

return False

发表于 2020-05-28 18:11:59 回复(0)

Python

牛客624277366号

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        for i in numbers:
            a = numbers.count(i)
            if a != 1:
                duplication[0] = i
                return True
            else:
                continue
        return False

发表于 2020-05-28 15:00:24 回复(0)

Python

Kuriyamaaa

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        n=numbers
        n.sort()
        for i in range(len(n)-1):
            for j in range(i+1,len(n)):
                if n[i]==n[j]:
                    duplication[0]=n[i]
                    return True
        return False
        # write code here

发表于 2020-05-27 21:19:09 回复(0)

Python

牛客124928456号

    def duplicate(self, numbers, duplication):
        # write code here
        d=[]
        for i in numbers:
            if numbers.count(i)!=1:
                if i not in d:                   
                    d.append(i)
        if len(d)==0:
            return('false')
        else:
            duplication[0]=d[0]
            return('true')

发表于 2020-05-22 17:34:19 回复(0)

Python

honeypomelo

from collections import Counter
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
dict_data = Counter(numbers)
duplication = [key for key, value in dict_data.items() if value > 1][0]
if duplication is not None:
return True
else:

return False

这个为啥不通过呀

发表于 2020-03-19 17:15:57 回复(0)

Python

刘摇滚

class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, L, duplication):
# write code here
for i in range(len(L)):
while L[i] != i:
if L[L[i]] == L[i]:
duplication[0] = L[i]
return True
tmp = L[i]
L[i]=L[L[i]]
L[tmp]=tmp
return False;

发表于 2020-02-27 23:01:02 回复(0)

Python

朝夕_

class Solution:
    def duplicate(self, numbers, duplication):
        for i in numbers:
            if numbers.count(i) > 1:
                duplication[0] = i
                return True
        return False

编辑于 2020-02-23 15:55:20 回复(0)

Python

菜鸟小白n

这种做法错在哪里了呢？？？

class Solution:

# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
shuchu=''
for i in range(0,len(numbers)):
for j in range(i+1,len(numbers)):
if numbers[i]==numbers[j]:
duplication[0]=numbers[i]
shuchu=True
break
if shuchu=='':
shuchu=False
return shuchu

发表于 2020-02-19 16:57:28 回复(0)

Python

结束校招

多年后刷题思路大变...

应该可以简化成one line python

每次用python都觉得自己在作弊....

class Solution:
    def duplicate(self, numbers, duplication):
        nums = set(numbers)
        for i in nums:
            if numbers.count(i) > 1:
                duplication[0] = i
                return True
        return False

发表于 2020-01-29 18:10:12 回复(0)

Python

天山剑客

# -*- coding:utf-8 -*-
# 解题思路：
# 以数组 {2,3,1,0,2,5,3} 为例
# 当 i = 0 时，nums[i] = 2 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{1,3,2,0,2,5,3}
# 此时 i = 0，nums[i] = 1 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{3,1,2,0,2,5,3}
# 此时 i = 0，nums[i] = 3 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{0,1,2,3,2,5,3}
# 此时 i = 0，nums[i] = 0 = i，继续下一组
# 当 i = 1，nums[i] = 1 = i，继续下一组
# 当 i = 2，nums[i] = 2 = i，继续下一组
# 当 i = 3，nums[i] = 3 = i，继续下一组
# 当 i = 4，nums[i] = 2 != i，判断 nums[i] 等于 nums[nums[i]]，出现重复，赋值返回
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        for i in range(len(numbers)):
            while numbers[i] != i:
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                else:
                    a = numbers[i]
                    numbers[i] = numbers[a]
                    numbers[a] = a

        return False

发表于 2020-01-16 11:25:55 回复(0)

Python

黄沙遮天

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if numbers==None:
            return False
        list1={}
        for i in numbers:
            a=numbers.count(i)
            if i not in list1:
                list1[i]=a
        if len(list1)==0:
            return False
        else:
            for keys,values in list1.items():
                if values>1:
                    duplication[0]=keys
                    return True
            return False

这道题的难点就是理解题的意思，其他没啥，利用列表的count函数进行各个数字的统计就行，剩下就是
注意便捷条件；只有那些values大于1的才会被选出来

发表于 2020-01-12 19:55:29 回复(0)

Python

少一块星空

# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找javascript:void(0);到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
numbers_set = []
for i in numbers:
if i not in numbers_set:
numbers_set.append(i)
else:
duplication[0] = i
return True
return False

发表于 2019-12-19 14:47:04 回复(1)

Python

卑微求offer的硕狗在读

不整花里胡哨的了，利用字典

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    # 垃圾题目，毁我青春
    def duplicate(self, numbers, duplication):
        # write code here
        dict={}
        duplication[0]=-1
        for i in range(len(numbers)):
            if numbers[i] in dict:
                duplication[0]=numbers[i]
                return True 
            else:
                dict[numbers[i]]=1   # dict[i]错误
        return False

发表于 2019-11-29 03:17:47 回复(0)