1

我在 C# 4.0 中工作，但遇到以下问题：

给定一个实数的有限集 S 和一个参数 k（不一定在该集中），找到S 中大于或等于 k ​​的最小数。

显然，我可以使用平衡二叉树来做到这一点。但是，在 C# 中没有实现这种数据结构可以帮助我。C# 中有哪些算法选项和可能的实现？

编辑：

由于大多数人对批评比真正帮助更感兴趣，所以我将解释更多：

它适用于将真实函数划分为数百万个片段（或箱，如直方图）的算法，我需要找到包含 k 的片段以及在其中应用一些计算的有效方法。这些片段是 [a; b) 并且不要重叠。

我正在设计的方法需要在给定 k 的情况下获取该部分，并且对于性能至关重要，因为它应该每秒调用数千次。因此，O(n) 搜索是不可接受的。

构建 S 的数据结构所浪费的时间并不重要，也不重要，因为该集合只会构建一次并且永远不会改变（它是一个不可变的集合）。

我知道我可以使用具有 O(log n) 搜索复杂度的红黑树。但是，我想研究其他算法选项（可能还有 C# 中的现有实现）。

4

4 回答 4

2

这个问题在 O(n) 时间内很容易解决。遍历所有元素，跟踪迄今为止发现的满足条件的最小元素（不小于 k）。

如果用不同的 k 重复：对有序数组进行二分搜索 O(log n)

如果最大元素大小是有界的，则类似于架构的桶排序将给出 O(1) 时间。

于 2012-10-10T20:20:48.230 回答
2

最简单的方法是 ( O(N)) ：

double k = 3.5;
List<double> S = new List<double>() { 1, 3, 5, 7, 9, 2, 4, 5, 6, 8, 10 };

var min = S.Where(f => f >= k).Min(); //4

如果您的列表已经排序，那么成本是O(LogN)

List<double> S = new List<double>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

var index = S.BinarySearch(k);
var min = index > 0 ? S[index] : S[~index];
于 2012-10-10T20:27:11.330 回答
1

好吧，您可以使用SCG.SortedSet，它在幕后是一棵红黑树。

您可以使用 SCG.List 或数组，对其进行排序并使用其BinarySearch()方法。

您也可以使用C5 Collections Library。

如果这是家庭作业，您可以推出自己的实现（可能是教授想要的，我想）。那里有很多选择。

于 2012-10-10T20:27:25.027 回答
0

不是“最快的”，但SortedList可能是“足够快”：

public static class Extensions
{
    public static double FindSmallestGreaterThan(this SortedList<double,double> list, double value)
    {
       foreach(double d in list.Keys)
       {
           if(d > value) return d;
       }
       throw new IndexOutOfRangeException("No values in the list greater than " + value.ToString());
    }
}

用法是：

SortedList<double,double> list = new SortedList<double,double>();
list.Add(0.5, 0.5);
list.Add(1.9, 1.9);

double d = list.FindSmallestGreaterThan(1.0);
于 2012-10-10T20:25:58.830 回答