O(1)从范围内的键中查找值
O(1)从范围内的键中查找值
提问于 2014-01-14 22:59:07
什么样的数据结构允许我从一组有序的类范围键()中从给定的键中获得相应的值，其中我的键不一定在集合中。
考虑，关键，价值
[3, 1]
[5, 2]
[10, 3]向上查找3或4将返回1，5-9将返回2，10返回3。范围为，而不是恒定大小的。
如果可能的话，O(1)或类-O(1)是重要的。
回答 3
Stack Overflow用户
发布于 2014-01-14 23:06:21
一个平衡的二叉树将给你O(log )。
Stack Overflow用户
发布于 2014-01-14 23:32:18
键索引数组呢？比方说，您知道您的键在1000以下，您可以简单地用值填充一个int[1000]，如: 0,0，2,0，4,1 .诸若此类。这将为您提供o(1)性能，但是内存开销很大。
否则，哈希表是我所知道的最接近的。希望能帮上忙。编辑:查找红黑树，它是一个自平衡树，在搜索中有最坏的O (logn)情况。
Stack Overflow用户
发布于 2014-01-14 23:26:14
在这种情况下，我会使用“我字典”。使用其键检索值非常快，接近O(1)
Dictionary<int, int> myDictionary = new Dictionary<int, int>();
myDictionary.Add(3,1);
myDictionary.Add(5,2);
myDictionary.Add(10,3);
//If you know the key exists, you can use
int value = myDictionary[3];
//If you don't know if the key is in the dictionary - use the TryGetValue method
int value;
if (myDictionary.TryGetValue(3, out value))
{
//The key was found and the corresponding value is stored in "value"
}欲了解更多信息：http://msdn.microsoft.com/en-us/library/xfhwa508.aspx
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/21125858
复制相关文章
相似问题
腾讯云开发者
