如何查找列表中是否包含Interval中的键

本文关键字：是否 包含 Interval 列表 何查找 查找 | 更新日期: 2024-09-25 18:45:42

我有一个<key,value>元素的排序列表。密钥是一个无符号整数

在C#中，有没有任何快速有效的方法来确定给定一个间隔，列表中是否包含一个在该间隔中带有键的元素？

如何查找列表中是否包含Interval中的键

一开始我没有注意到您的列表是排序的

似乎有可能，是的，在O（log N）中

假设你的音程是[A，B]
假设你有数字C1，C2。。。
中的CNlist和C[K]<=每个K的C[K+1]。

1） 求极小K1使得C[K1]>=A
如果未找到K1，则答案为"未找到"
2） 求最大K2，使得C[K2]<=B
如果未找到K2，则答案为"未找到"
3） 最后，如果K1<K2答案为"已找到"，
否则答案为"未找到"

对于1）和2），我认为可以使用二进制搜索。
所以你所需要做的就是用C#来编写这个代码

如果您的列表包含整正数，那么您可以使用LINQ Any、Enumerable.Range非常容易地构建自己的函数来创建要检查的范围和list.contains。代码如下所示：

var list = new List<int> { 1, 2, 3, 4, 5, 10, 100, 1000 };
// range to check
var min = 15;
var max = 18;
Console.WriteLine(list.Any (l => Enumerable.Range(min, max - min).ToList().Contains(l)) ? "Yes" : "No");

输出适用于[15-18]否和[9-11]是。

另一种可能性（比第一种更快）是@peter.petrov建议直接在给定的时间间隔内搜索（使用列表上的LINQ where子句）：

var list = new List<int> { 1, 2, 3, 4, 5, 10, 100, 1000 };
// range to check
var min = 15;
var max = 18;
Console.WriteLine(list.Where (l => l > min && l < max).ToList().Count() > 0 ? "Yes" : "No");

输出与第一个代码示例中的相同。

这种方法可以应用于任何实现IEnumerable接口的类。使用SortedList的一个解决方案如下所示：

var list = new SortedList<int, int> { {1, 1}, {2, 2}, {3, 3}, {4, 10}, {5, 100} };
// range to check
var min = 15;
var max = 18;
Console.WriteLine(list.Where (l => l.Value > min && l.Value < max).ToList().Count () > 0 ? "Yes" : "No");

SortedList有一个名为ContainKey()的方法，它确定SortedList对象是否包含特定键，并且是使用o（log N）内部确定的，因为带下划线的实现使用的是二进制搜索树。然而，在您的情况下，它是一系列关键点。所以我建议你写一个二进制搜索你的范围。

这将是最快的解决方案，因为SortedList.ContainsKey实现了Dictionary.Contains Key，并且它已经是一个O（logn）操作。如果你只是想成为会员，你也可以在第一场比赛中保释。

SortedList<uint, int> n = new SortedList<uint, int>();
private bool KeyInRange(uint rangemin, uint rangemax;){
    for (uint i=rangemin; i<=rangemax; i++)
        if(n.ContainsKey(i))
            return true;
    return false;
}
相关文章：