查找數組中的重複元素？

一個數組數爲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

查找數組中的重複元素？

回答

相關問題