在数组中寻找重复元素？

Question

我看到一个关于面试问题的提问：

在数组中有一个重复的数字，请找出它。

以下是简单的解决方案：

for(int i=0;i<n;i++){
{  
    dup = false;
    for(j=0;j<n;j++){
        if(i!=j && a[i]= a[j]){
            dup = true;
        }

       if(dup == true)
          return a[i]
     }
}

但我希望以O(n log(n))和O(n)的时间复杂度实现它。怎样才能做到呢？

- mindtree

---

你是用C++还是Java编程？如果你的问题与语言无关，请删除特定于语言的标签。 - GManNickG

Answer 1

对数组进行排序（可以在第一次O(n log n)中完成），然后只需为相邻的元素进行比较。或者将数组放入哈希表中，如果发现第一个具有现有条目的键，则停止。

- Friedrich

---

当使用集合时，为什么要这样做，因为它的时间复杂度接近O(n)？ - Cary Swoveland

Answer 2

我正在回答“如何在数组中找到重复元素？”

你需要从0到n搜索i和j，然后检查j！= i。相反，您可以像这样形成循环：

for (int i=0; i<n-1; i++) 
{
    for (j=i+1; j<n; j++)
    {
         if (a[i] == a[j])
         {
            return i;
         }
    }
}
return -1; 

重复设置dup=false是无意义的。要么dup仍然为false，要么它曾经为true，然后你用'return'离开了代码。

- user unknown

Answer 3

以下是Java代码，时间复杂度为O(n log n)：

    Arrays.sort(arr);
    for (int i = 1; i < arr.length; i++)
        if (arr[i] == arr[i - 1])
            return arr[i];
    throw new Exception(); // error: no duplicate

O(n)时间：

    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < arr.length; i++) {
        if (set.contains(arr[i]))
            return arr[i];
        set.add(arr[i]);
    }
    throw new Exception(); // error: no duplicate

- Rui Gonçalves

---

基于哈希表的数据结构如果存在冲突，最坏情况下的时间复杂度可能为O(n^2)。由于红黑树是自平衡树，所以基于树的数据结构的最坏情况时间复杂度将为O(nlogn)。 - Tarun

将 Set<Integer> set = new HashSet<>(arr.length); 这样写（如果重复的概率接近开头很低 - 如果高，最好使用 Set 的树实现）。使用 foreach 循环。只需添加元素并返回 !Set.add(arr[i]) 即可。 - greybeard

Answer 4

我建议使用哈希表（假设没有冲突）来解决它。

 private boolean hasDuplicate(int[] arr) {
        Map<Integer, Boolean> map = new HashMap();
        // find the duplicate element from an array using map
        for (int i = 0; i < arr.length; i++) {
            if(map.containsKey(arr[i])) {
                return true;
            } else {
                map.put(arr[i], true);
            }
        }
        return false;
    }

时间复杂度：O(n)

空间复杂度：O(n)

另一种方法是排序和比较，但排序会增加额外的开销。

- Sri

Answer 5

参考 java.util.TreeSet，它是基于红黑树实现的，时间复杂度为 O(n*log(n))。

- 卢声远 Shengyuan Lu

Answer 6

通过使用集合，我们可以采用以下代码片段 -

Set<String> set = new HashSet<String>();
    for (String arrayElement : arr) {
        if (!set.add(arrayElement)) {
            System.out.println("Duplicate Element is : " + arrayElement);
        }
    }

- Sachchidanand Singh

Answer 7

找到以下O(n)复杂度的解决方案 -

int ar[]={0,1,2,3,0,2,3,1,0,2};
    Set  <Integer>mySet=new HashSet<>();
    for(int n:ar){
        if(!mySet.add(n)){
            System.out.println(" "+n);
        }
    }

还有另一个进程，其空间复杂度较低为O(N)，可能为O(n Log n) --

    public void duplicateElementSolution(int ar[]){
     Arrays.sort(ar);

    for(int i=0;i<(ar.length-1);i++){
        if(ar[i]==ar[i+1]){
            System.out.println(" "+ar[i]);
        }
    }
  }

- pkm1986

Answer 8

（当前形式的问题有点令人困惑-我的答案假设问题是找到数组中两个数的和等于给定值）

由于给定的数组是未排序的，我假设我们不允许对数组进行排序（即不能改变数组的给定顺序）。

我认为最简单的解决方案是遍历每个数字x并检查数组中是否存在I-x。这本质上就是你的O(n^2)解决方案所做的。

通过使用某种快速集数据结构使搜索更快，可以将其降低到O(n)或O(nlogn)。基本上，当我们遍历数组时，我们查询I-x是否在集合中出现。

代码（用Python编写）：

l=[1,2,3,4,5,6,7,8,9]
seen=set()

I=11
for item in l:
        if I-item in seen:
                print "(%d,%d)"%(item,I-item)
        seen.add(item)

解决方案的复杂度取决于所使用的“set”数据结构的插入/查找复杂度。基于哈希表的实现具有O(1)复杂度，因此它提供了O(n)算法，而基于树的“set”会产生O(nlogn)算法。

编辑：

相当于Python中的“set”的数据结构是C++中的“stl::set”和Java中的“TreeSet”/“HashSet”。行“I-x in seen”将翻译为Java中的“seen.contains(I-x)”和C++中的“seen.find(I-x)==seen.end()”。

- MAK

---

我不太理解它，也不太熟悉Python。你只是在集合中添加项目，我们如何在这段代码中找到sum = i呢？ - mindtree

@mindtree：就像我在代码前的解释中所说，如果a+b=X，那么我们有b=X-a。因此，我们只需要检查X-a是否在之前遇到的数字集合中（使用表达式I=item in seen）。 - MAK

问题已经被编辑，偏离了这个假设，所以最好删除这个答案。 - Bernhard Barker