卸下列表

Question

我想創造，將篩選出的列表的所有非獨特成員的方法，所有的非唯一成員，使得與輸入

3 5 3 8 8 2列表

將成爲

I H廣告的想法嘗試以下內容：

private static List<Integer> getUniques(List<Integer> list) { 
     for (Integer n : list) { 
      list.remove(n); 
      if (!list.contains(n)) { 
       list.add(n); 
      } else { 
       while (list.contains(n)) { 
        list.remove(n); 
       } 
      } 
     } 
     return list; 
    } 

但是，這引發了併發修改異常。我做了一個工作調整：

private static List<Integer> getUniques(List<Integer> list) { 
     List<Integer> result = new ArrayList<>(); 
     Set<Integer> distinctSet = new HashSet<>(); 

     distinctSet.addAll(list); 
     result.addAll(list); 

     for (Integer n : distinctSet) { 
      result.remove(n); 
      if (!result.contains(n)) { 
       result.add(n); 
      } else { 
       while (result.contains(n)) { 
        result.remove(n); 
       } 
      } 
     } 
     return result; 
    } 

這完成了我想要的，但似乎有點複雜/效率低下。我有沒有辦法以我想到的第一種方式來做到這一點？或者另一種更有效的方法呢？還是我已經基本上使用最好的方法？

Answer 1

一個更好的辦法是使用HashMap來標記元素之前保持，然後基於此添加。這種方法是O(N)，它比您的解決方案的O(N^2)更好（根據傳入的List實現，刪除可能爲O(N)）。如果這一點很重要，它肯定會保留原始列表中元素的排序。

private static List<Integer> getUniques(List<Integer> list) { 
    HashMap<Integer, Boolean> flagMap = new HashMap<>(); 

    //Total Loop: O(N) 
    for(Integer i : list){ 
     if(flagMap.containsKey(i)) flagMap.put(i, false); //O(1) 
     else flagMap.put(i, true); //O(1) 
    } 

    ArrayList<Integer> result = new ArrayList<Integer>(); 

    //Total Loop: O(N) 
    for(Integer i : list){ 
     if(flagMap.get(i)) result.add(i); //O(1) 
    } 
    return result; 
} 

Answer 2

我建議你先用一種方法來計算一個項目出現在List的次數。像

private static <T> int count(List<T> al, T val) { 
    int r = 0; 
    for (T t : al) { 
     if (t.equals(val)) { 
      r++; 
     } 
    } 
    return r; 
} 

東西然後創建一個新的List返回，並檢查count是1，你把它添加到List像

private static List<Integer> getUniques(List<Integer> list) { 
    List<Integer> al = new ArrayList<>(); 
    for (Integer n : list) { 
     if (count(list, n) == 1) { 
      al.add(n); 
     } 
    } 
    return al; 
} 

Answer 3

使用Java 8，您可以使用流API執行Mshnik正在做的事情。但是，由於這仍然是一個新的API，您可能需要在工作時謹慎使用它。可讀性（由你和你的同行）應該勝過簡潔。如果使用Java 8 /流API不是一種選擇，那麼Mshnik的解決方案就是我的選擇。

List<Integer> uniques = 
    list.stream(). 
     collect(Collectors.groupingBy(i -> i, Collectors.reducing(0, (a, b) -> a + b))). //Adding all occurances of that number {3->6, 5->5, 8->16, 2->2} 
     entrySet().stream(). //The above map's entries as a set 
     filter(e -> e.getValue() == e.getKey()). //Retains {5->5, 2->2} 
     map(e -> e.getKey()). //Retains {5, 2} 
     collect(Collectors.<Integer>toList()); //Collects 

注意，儘管每行可能看起來另一迭代在列表中，這實際上是一個2通溶液（第一遍是，當我們收集作爲地圖和所述第二遍時我們所收集的列表）。

複雜度：預計 O（N） - 作爲分組將通過使用HashMap。