c# - 将数组中的值与数组中之前的所有值进行比较的有效方法

Question

我有一个很长的数组 numbers[]。我的算法需要在 numbers[] 中找到 |numbers[j] - numbers[i]| <= x 所在的最低索引 j (随机变量)或 |numbers[j] - numbers[i]| >= m - x (m 另一个变量，大于 x)，其中 i<j .

现在这是我的算法:

 for (int j = 1; j < numbers.Length; j++)
 {
     for (int i = 0; i < j; i++)
     {
        long diff = Math.Abs(numbers[j] - numbers[i]); 
        if (diff <= x || diff >= m - x)
            return j;
     }
 }

这可以更有效地完成吗？例如，一个非常大的数字输入需要我的笔记本电脑大约 36 秒。

Answer 1

您可以通过遍历数组并在每个阶段将新数字添加到平衡搜索树来在 O(nlogn) 中完成此操作。

当您添加号码时，您首先要搜索搜索树中已有的最接近的号码。如果这个数字小于目标差异，那么您就找到了答案。