我正在尝试按另一个数组中定义的顺序对字符串列表进行排序。我知道可以通过多种方式实现,但我不确定如何有效地做到这一点。我需要它能够处理一个包含数千个项目的大型未排序列表。这是我想出的:
List<string> sortStringListByArray(List<string> unsortedList, string[] order)
{
List<string> sortedList = new List<string>();
for(int i = 0; i < order.Length; i++)
{
foreach(string s in unsortedList)
{
if(s.Equals(order[i]))
{
sortedList.Add(s);
}
}
}
return sortedList;
}
它按预期工作,但效率肯定不高。有什么方法可以在不遍历列表和订单的情况下执行此操作?
编辑:澄清
谢谢!
最佳答案
表示它的最简单方法是使用右内连接:
return order.Join(unsortedList, a => a, b => b, (a, b) => b).ToList();
使用 Lookup 或 Dictionary 的最佳时间复杂度是 O(n+m) :
var lookup = unsortedList.ToLookup(x => x);
return order.SelectMany(x => lookup[x]).ToList();
使用 Dictionary<string, int>
可以使上面的速度快几倍获取 unsortedList
中的项目计数, 然后遍历 order
根据counts Dictionary中对应的值生成结果。
Lookup
和 Dictionary
使用 hash table存储值。为了在哈希表中找到一个项目,从该值计算出一个哈希值,这类似于该值在哈希表中的位置的估计位置/索引。这只允许在哈希表中查找(或不查找)值所需的 1 次或少量比较。因此,从 unsortedList
生成查找或字典的时间复杂度为 O(n) , 因为哈希表的平均查找时间为 O(1)
关于c# - 按数组中定义的顺序对字符串列表进行排序的有效方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56827070/