删除不同索引中相同成员的列表

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)