c# - 使用连接计数数组在数组中的索引处查找项目的有效方法

Question

我有一个包含两个数组的对象，第一个是斜率数组:

double[] Slopes = new double[capacity];

接下来是一个包含各种斜率计数的数组:

int[] Counts = new int[capacity];

数组是相关的，因为当我向对象添加斜率时，如果斜率数组中输入的最后一个元素与新项目的斜率相同，而不是将其添加为新元素，则计数会递增。

即如果我有斜坡 15 15 15 12 4 15 15，我得到:

Slopes = { 15, 12, 4, 15 }
Counts = {  3,  1, 1,  2 }

有没有比使用索引遍历 Counts 并在 Slopes 中找到相应索引更好的方法来查找 slopes 中的第 i_th 项？

编辑:不确定我的问题是否不清楚。我需要能够访问发生的第 i_th 个斜率，因此从示例中出现的零索引 i = 3 斜率是 12，问题是是否存在更有效的解决方案来找到新结构中的相应斜率。

也许这将有助于更好地理解问题:这是我现在如何获得第 i_th 个元素:

public double GetSlope(int index)
        int countIndex = 0;
        int countAccum = 0;
        foreach (int count in Counts)
        {
            countAccum += count;
            if (index - countAccum < 0)
            {
                return Slopes[countIndex];
            }
            else
            {
                countIndex++;
            }
        }
        return Slopes[Index];
}

请问有没有更高效的方法？

Answer 1

您可以使用第三个数组来存储重复斜率的第一个索引

double[] Slopes = new double[capacity];
int[] Counts = new int[capacity]; 
int[] Indexes = new int[capacity]; 

与

Slopes  = { 15, 12, 4, 15 }
Counts  = {  3,  1, 1,  2 } 
Indexes = {  0,  3, 4,  5 } 

现在您可以在 Indexes 中应用二进制搜索来搜索小于或等于您要查找的索引的索引。

您现在的搜索性能不是 O(n)，而是 O(log(n))。