刪除不同索引中相同成員的列表

Question

假設我有一個List<List<Integer>>，它包含從1到n的數字列表。用相同的成員，但在不同的索引中刪除列表的好方法是什麼？

如果我有[[1,2,3], [2,1,3], [4,5,6]]，我正在考慮將第一個和第二個成員作爲重複項，並且我想刪除其中的一個（無論哪一個）以獲得[[2,1,3], [4,5,6]]或[[1,2,3], [4,5,6]]。

有一個O(n^2)解決方案通過所有成員循環使用list.contains(x)甚至使用List<Set<Integer>>，但我不知道是否有更好的解決辦法來做到這一點。

Answer 1

這樣做的一種方法是散列每個列表，然後使用相同的散列檢查更仔細的列表。有許多這樣做的方法：

1. 如果你建立從列表中的元素的XOR散列，則散列較弱，但廉價的構建，因爲它是獨立於訂單列表中的元素。如果每個列表有n列表和k項目，則構建哈希值僅爲Θ（n k），這是非常便宜的。當然，需要比較具有相同散列的列表，並且此方法的弱散列可能會導致比所需更多的衝突。

2. 如果排序每個列表，然後建立從排序結果的哈希，哈希會更強，但是建立哈希將採取Θ（Nķ日誌（K））。

更好的方法取決於設置。

Answer 2

算法概括地說：

1. 項目外列表的每個元素到散列和索引的元組。元組相對於它的第一個元素（散）的元組
2. 提取指數與原來的哈希

下面的代碼

排序列表實現了這個算法

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 

static class Program 
{ 
// Computes hash of array (we suppose, that any array has the fixed length) 
// In other words, we suppose, that all input arrays have the same length 
static int array_hash(int[] array) 
{ 
    int hc = array.Length; 
    for (int i = 0; i < array.Length; ++i) 
    { 
     hc = unchecked(hc * 314159 + array[i]); 
    } 
    return hc; 
} 
static void Main(string[] args) 
{ 
    var lists = new List<List<int>>(); 
    lists.Add(new List<int>() { 1, 2, 3 }); 
    lists.Add(new List<int>() { 3, 2, 1 }); 
    lists.Add(new List<int>() { 4, 5, 6 }); 

    var hashs = new List<Tuple<int, int>>(lists.Count); 

    for (int i= 0; i < lists.Count; ++i) 
    { 
     var inner_list_copy = lists[i].ToArray(); 
     Array.Sort(inner_list_copy); 
     hashs.Add(Tuple.Create(array_hash(inner_list_copy), i)); 
    } 
    hashs.Sort((tuple1, tuple2) => tuple1.Item1.CompareTo(tuple2.Item1)); 
    var indices = new List<int>(); 
    var last_hash = 0; 
    if (hashs.Count != 0) 
    { 
     last_hash = hashs[0].Item1; 
     indices.Add(hashs[0].Item2); 
    } 
    for (int i = 1; i < hashs.Count; ++i) 
    { 
     var new_hash = hashs[i].Item1; 
     if (new_hash != last_hash) 
     { 
      last_hash = new_hash; 
      indices.Add(hashs[i].Item2); 
     } 
    } 
    Console.WriteLine("Indices"); 
    for (int i = 0; i < indices.Count; ++i) 
    { 
     Console.WriteLine(indices[i]); 
    } 

    Console.ReadLine(); 
} 
} 

注意：您可以探索使用其他散列函數。見C# hashcode for array of ints

P.S.只是爲了好玩 - 在haskell中的解決方案

-- f - removes duplicates from list of lists via sorting and grouping 
f = (map head) . group . (map sort)