给定n个整数的数组中的重复[关闭]

Question

想改进这个问题吗？更新问题，使其仅通过编辑这篇文章来关注一个问题。

你能展示一下你是否得到了一个由n个整数组成的数组吗。数组中的整数介于1和n-1之间。必须找到重复的整数。你需要在O（n）时间内完成，但你可以使用额外的空间。

输入格式：输入包含数组中的元素数，后跟数组中的元素。

输出格式：输出返回重复的整数，如果没有重复，则返回-1。

示例测试用例：

输入：5 1 4 3 2 3

输出：3

输入4 1 3 2 1

输出：1

Answer 1

假设这里有一个重复的算法---

（1） 创建阵列频率计数（1到n-1）。

（2） 仅扫描输入阵列一次，如果输入阵列中的第i个元素为m，则增加频率计数（m）。

（3） 扫描结束时，FrequencyCount中只有一个元素将为2，FrequencyCount中的每个其他元素将为1。

（4） 所以扫描FrequencyCount数组，如果数组中的第k个元素是2，那么唯一的重复项是k。

' Assuming , there will be exactly one duplicate
' here is VBA code

Function FindTheFuplicate(a() as integer) as integer
    dim n as integer, i as integer, m as integer
    n = ubound(a)
    redim FrequencyCount(1 to ubound(a)-1)
    for i = 1 to n
        'take the number in m
        m = a(i)
        FrequencyCount(m) = FrequencyCount(m) + 1 
    next i
    ' now exactly one FrequencyCountwill be 2 
    ' and all other FrequencyCount will be ONE
    for i = 1 to n - 1
         if FrequencyCount(i) = 2  then
             debug.print ("Duplicate = " & i )
             FindTheFuplicate = i
             exit function  
         end if
    next i
End Function

Answer 2

有很多选择：

• 排序并检查两个相同的连续元素
• 使用从1到（n-1）（即（n-1）（n）/2）的整数和的公式，并求数组中每个元素的和。不同之处在于重复元素
• 在遍历数组时，使用哈希集检查重复元素

Answer 3

这里最主要的是每个数字需要恰好出现一次。你可以这样做：

1. 创建一个大小为n的新空数组，初始化为“0”
2. 检查原始数组，为在原始数组中找到值的新数组中的每个索引写入“1”
3. 如果有任何单元格/存储桶具有值，请检查新数组

这是O（n）的整体时间复杂度和O（n）的空间