C++中的一組列表

鑑於候選人編號（C）和目標數（T）的集合中刪除重複，發現在所有的獨特組合C，其中候選號碼總和爲T.

C中的每個數字只能在組合中使用一次。

注：

所有號碼（包括目標）將是正整數。
組合中的元素（a1，a2，...，ak）必須爲非降序。（即a1≤a2≤...≤ak）。
該解決方案集不能包含重複的組合。

例如，給定候選集10,1,2,7,6,1,5和目標8，的溶液組是：

[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6]

我的問題是如何有效地除去重複？以下是我的代碼：

public class Solution { 
    public static void main(String[] args) { 
     int[] input = { 10, 1, 2, 7, 6, 1, 5 }; 
     // int[] input = { 2, 1, 1, 4, 4, 2 }; 
     System.out.println(combinationSum2(input, 8)); 
    } 

    private static class Entry { 
     List<Integer> list; 
     int target; 
     int index; // the previous index 

     public Entry(int target) { 
      list = new LinkedList<Integer>(); 
      this.target = target; 
     } 

     public int add(int num, int index) { 
      this.list.add(num); 
      this.index = index; 
      this.target -= num; 
      return target; 
     } 

     public Entry copy() { 
      Entry copy = new Entry(this.target); 
      copy.list = new ArrayList<>(); 
      copy.list.addAll(list); 
      copy.target = target; 
      copy.index = index; 
      return copy; 
     } 

    } 

    public static List<List<Integer>> combinationSum2(int[] input, int target) { 
     List<List<Integer>> ret = new LinkedList<List<Integer>>(); 

     if (null == input || input.length <= 0) 
      return ret; 

     Arrays.sort(input); 

     int N = input.length; 
     Queue<Entry> pool = new LinkedList<Entry>(); 
     for (int i = 0; i < N; i++) { 
      if (input[i] <= target) { 
       Entry entry = new Entry(target); 
       entry.add(input[i], i); 
       pool.add(entry); 
      } 
     } 

     while (!pool.isEmpty()) { 
      Entry cur = pool.poll(); 
      if (cur.target == 0) { 
       ret.add(cur.list); 
      } else if (cur.target > 0) { 
       for (int i = cur.index + 1; i < N; i++) { 
        if (cur.target - input[i] >= 0) { 
         Entry copy = cur.copy(); 
         copy.add(input[i], i); 
         pool.offer(copy); 
        } else { 
         break; 
        } 
       } 
      } 
     } 

     return ret; 
    } 
}

我的第一個想法是在返回列表中的列表進行排序，比較它們一個一個地刪除重複。但有沒有更快的方法？或任何建議？

來源

2014-12-22 1736964698

我的建議是使用HashSet來防止添加任何現有的條目。首先要做的是覆蓋Entry類的equals和hashCode函數。（more material）

private static class Entry { 
    List<Integer> list; 
    int target; 
    int index; 
    int hash; // <---- add this 

    public Entry(int target) { 
     list = new LinkedList<Integer>(); 
     this.target = target; 
     hash = target; 
    } 

    public int add(int num, int index) { 
     this.list.add(num); 
     this.index = index; 
     this.target -= num; 
     hash = hash * 17 + num; 
     return target; 
    } 

    public Entry copy() { 
     Entry copy = new Entry(this.target); 
     copy.list = new ArrayList<>(); 
     copy.list.addAll(list); 
     copy.target = target; 
     copy.index = index; 
     copy.hash = hash; 
     return copy; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     Entry e = (Entry) obj; 
     if ((this.target != e.target) || (this.list.size() != e.list.size())) { 
      return false; 
     } 
     for (int i = 0; i < this.list.size(); i++) { 
      if (!this.list.get(i).equals(e.list.get(i))) 
       return false; 
     } 
     return true; 
    } 

    @Override 
    public int hashCode() { 
     return hash; 
    } 
}

下一步是使用哈希集過濾結果。

Set<Entry> nodup = new HashSet<Entry>(); 

while (!pool.isEmpty()) { 
    Entry cur = pool.poll(); 
    if (cur.target == 0) { 
     nodup.add(cur); 
    } else if (cur.target > 0) { 
     // ... your code 
    } 
} 

for (Entry entry : nodup) { 
    ret.add(entry.list); 
}

來源

2014-12-22 04:23:57

您可以使用散列作爲另一種解決方案，雖然它將在空間（時間相同）方面使用O(n)。

基本上，從頭到尾遍歷列表。對於每個新遇到的元素，我們檢查它是否在哈希集合（HashSet）中：如果是，我們將其刪除;否則我們把它放進去。

來源

2014-12-22 04:16:32

通過將List轉換爲Java中的HashSet，您可以從Java List中刪除重複或重複的元素。但是在做之前，請記住，Set不保證List的插入順序，實際上這是List和Set之間在Java中的主要區別。

因此，當您將List轉換爲HashSet時，所有重複元素都將被刪除，但插入順序將丟失。

更詳細的解釋可以參見here

來源

2014-12-22 07:10:07 4384034

C++中的一組列表

回答

相關問題