查找数组中的重复元素？

一个数组数为duplicating.Find它

简单的解决方案如下：

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）时间。我该怎么做？

来源

2011-02-04 mindtree

你用C++或Java编程？如果您的问题与语言无关，请移除特定于语言的标签。 – GManNickG 2011-02-04 06:35:41

对数组进行排序（可以在第一个O（n Log n）中完成），然后只需对相邻元素进行比较，或者将数组放入散列表中，如果发现第一个。与exsting输入键

来源

2011-02-04 06:12:45 Friedrich

参考java.util.TreeSet其上实现了红黑树的底层，它是为O（n *的log（n））

来源

2011-02-04 06:15:20

-1

（目前形式的问题是有点混乱。 - 我的答案是假定问题是关于在数组中找到两个数字，总和为给定值）

既然给定的数组是未排序的，我假设我们不允许排序数组（即数组的给定顺序不能改变）。

最简单的解决方案恕我直言，是遍历每个数字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和爪哇TreeSet/HashSet。行I-x in seen将转换为Java中的seen.contains(I-x)和C++中的seen.find(I-x)==seen.end()。

来源

2011-02-04 06:42:28 MAK

我不理解它，对python.U不太熟悉，我只是添加了一个项目来设置，我们如何在这个代码中找到sum = i？ – mindtree 2011-02-04 06:48:58

@mindtree：正如我在代码前面的解释中所说的，如果a + b = X，我们有b = X-a。所以我们只检查X-a是否在前面遇到的数字集合中（使用表达式'I = item in seen`）。 – MAK 2011-02-04 08:33:14

我回答“查找数组中的重复元素？”

您搜索i和j从0到< n，然后您检查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仍然是假的，或者它是真的，那么你用'return'离开了代码。

来源

2011-02-04 07:07:37

写在实际的代码前面的答案（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

来源

2011-02-04 15:01:46

我推荐使用散列图（假设没有冲突）来解决它。

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）的

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

来源

2014-07-17 12:05:58 Sriram

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

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

来源

2015-07-06 06:09:40

查找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日志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]); 
     } 
    } 
    }

来源

2017-01-15 14:54:11 pkm1986

查找数组中的重复元素？

回答

相关问题