3

假设我有这个数组（它实际上是 255 长，值高达 int.MaxValue）：

int[] lows = {0,9,0,0,5,0,0,8,4,1,3,0,0,0,0};

从这个数组中，我想获得一个等于或小于我的数字的值的索引。

number = 7 -> index = 4
number = 2 -> index = 9
number = 8 -> index = 7
number = 9 -> index = 1

找到它的最快方法是什么？

到目前为止，我使用了线性搜索，但结果证明这对我的需要来说效率太低了，因为即使这个数组只有 255 长，值也会被搜索几百万次。

我需要与 java 中使用的TreeSet.floor(E)相同的东西。我想使用Dictionary，但我不知道它是否可以找到我需要的第一个较小或相等的值。

4

4 回答 4

3

对数组进行排序，然后进行二进制搜索以查找值。

看：

https://en.wikipedia.org/wiki/Binary_search

和

Array.BinarySearch 方法

于 2012-11-04T00:59:57.360 回答
1

如果它没有排序（或者保存在可以帮助搜索的成员之间存在关系的数据结构中），那么您将不得不检查每个成员以找到正确的成员。

最简单的解决方案可能是对其进行排序，然后进行二分切/搜索以找到符合您条件的元素。

如果您想提高仍然采用未排序数组的能力，请sorted在数组的某处维护一个标志（即，将整个事物转换为包含指标和数组的类），以指示列表已排序。

false然后在数组更改时将此标志设置为。

在您想要进行搜索的地方，您首先检查sorted标志并对数组进行排序（如果它设置为） false（将其设置true为该过程的一部分）。如果标志是true，则绕过排序。

这样，您只在需要时进行排序。如果数组自上次排序后没有改变，则重新排序没有意义。

如果用户需要，您还可以维护原始的未排序列表，将排序列表保留为类中的附加数组（对数组进行分类的另一个优点）。这样，你什么都不会失去。您拥有可供用户获取的原始未触及数据，以及一种快速有效地找到所需元素的方法。

您的对象（排序后）将包含：

int[] lows       = {0,9,0,0,5,0,0,8,4,1,3,0,0,0,0};
int[] sortedlows = {0,0,0,0,0,0,0,0,0,1,3,4,5,8,9};
boolean isSorted = true;

如果您随后更改that_object[0]为3，您最终会得到：

int[] lows       = {3,9,0,0,5,0,0,8,4,1,3,0,0,0,0};
int[] sortedlows = {0,0,0,0,0,0,0,0,0,1,3,4,5,8,9};
boolean isSorted = false;

表示在搜索之前需要排序sortedLows。

请记住，将其变成课程并不是必需的。如果您担心它的性能（特别是通过 getter 方法访问数组元素），您可以维护数组并标记自己，同时仍然允许直接访问未排序的数组。您只需确保代码中更改数组的每个位置也正确设置了标志。

但是你应该在走这条路之前测量性能。基于类的方式“更安全”，因为对象本身控制着整个事物。

于 2012-11-04T01:00:42.463 回答
1

首先，规范化数据：

public static Dictionary<int, int> GetNormalised(int[] data)
{
    var normalised = data.Select((value, index) => new { value, index })
        .GroupBy(p => p.value, p => p.index)
        .Where(p => p.Key != 0)
        .OrderBy(p => p.Key)
        .ToDictionary(p => p.Key, p => p.Min());
    return normalised;
}

搜索方法：

public static int GetNearest(Dictionary<int, int> normalised, int value)
{
    var res = normalised.Where(p => p.Key <= value)
        .OrderBy(p => value - p.Key)
        .Select(p => (int?)p.Value)
        .FirstOrDefault();

    if (res == null)
    {
        throw new ArgumentOutOfRangeException("value", "Not found");
    }

    return res.Value;
}

单元测试：

[TestMethod]
public void GetNearestTest()
{
    var data = new[] { 0, 9, 0, 0, 5, 0, 0, 8, 4, 1, 3, 0, 0, 0, 0 };
    var normalised = Program.GetNormalised(data);

    var value = 7;
    var expected = 4;
    var actual = Program_Accessor.GetNearest(normalised, value);
    Assert.AreEqual(expected, actual);

    value = 2;
    expected = 9;
    actual = Program_Accessor.GetNearest(normalised, value);
    Assert.AreEqual(expected, actual);

    value = 8;
    expected = 7;
    actual = Program_Accessor.GetNearest(normalised, value);
    Assert.AreEqual(expected, actual);

    value = 9;
    expected = 1;
    actual = Program_Accessor.GetNearest(normalised, value);
    Assert.AreEqual(expected, actual);        
}

优化性能缓存所有使用的结果。

于 2012-11-04T03:15:47.063 回答
1

要在 C# 中模拟 Java TreeSet，请使用 C# 类：SortedDictionary 或 SortedSet；Java TreeSet 中的 mock floor 方法，使用 LINQ 方法，获取最小值。排序集数据 = 新排序集（）；data.Where(p =>p < 价格[i]).OrderByDescending(p=>p).Take(1)

基于 HackerRank 最小成本算法，Java TreeSet 实现方案运行良好，但 C# SortedDictionary，SortedSet 超时。
详情见我的编码博客：http: //juliachencoding.blogspot.ca/2016/11/c-sorteddictionary-minimum-cost.html

因此，C# SortedSet 类 GetViewBetween 可以做同样的事情。请参阅GetViewBetween API

有一个帖子：SortedSet / SortedList with better LINQ performance?

于 2016-11-21T20:27:57.200 回答