在具有联接计数数组的数组中查找索引处的项的有效方法

本文关键字：数组 索引 查找 方法 有效 数数 | 更新日期: 2023-09-27 18:22:11

我有一个对象，它包含两个数组，第一个是斜坡数组：

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中找到相应的索引更好的方法来找到斜率中的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];
}

我想知道是否有更有效的方法？

在具有联接计数数组的数组中查找索引处的项的有效方法

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

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））。

如果您一次加载斜率并执行许多"第i项"查找，那么使用第三个（或不是计数，具体取决于它的用途）数组来查找总数可能会有所帮助。对于您的示例，这将是{ 0, 3, 4, 5 }。然后你不需要每次查找都把它们加起来，这只是一个"i在Totals[x]和Totals[x+1]之间"的问题。如果你希望有几个斜率桶，或者在整个处理过程中添加斜率，或者如果你不做很多这样的查找，那么它可能不会给你带来任何好处。从本质上讲，这只是在前面一次性完成所有这些添加。

您总是可以将现有的数组和另一个数组（称为OriginalSlopes）包装成一个类。当您添加到Slopes时，您也会像添加普通数组一样添加到OriginalSlopes（即始终追加）。如果您需要i_th斜率，请在OriginalSlopes中查找。O（1）运算。

编辑添加示例数据：

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

在count对象（或基中的数组）中，添加一个变量，该变量具有迄今为止找到的cumulative count。

使用二进制搜索与comparator方法比较cumulative count，您将能够找到O（log N）时间的斜率。

编辑

`Data = 15 15 15 12 4 15 15`
Slopes = { 15, 12, 4, 15 }
Counts = {  3,  1, 1,  2 }
Cumulative count = { 3, 4, 5, 7}

例如，如果您正在寻找第6位的元素，当您搜索Cumulative count数据集并找到值5，并且知道下一个值是7时，您可以确保该索引处的元素也将具有第6位元素。

使用二进制搜索来查找log（N）时间中的元素。

为什么不使用Dictionary<double, double>，其中key为斜率，value为计数？

嗯，两双？现在我需要一杯咖啡。。。

编辑：您可以使用一个字典，其中键是斜率，每个键的值是相应索引和计数的列表。类似于：

class IndexCount
{
    public int Index { get; set; }
    public int Count { get; set; }
}

您的收款申报看起来像：

var slopes = new Dictionary<double, List<IndexCount>>();

然后，您可以按值查找字典，并从关联的集合中查看每个索引的计数。这可能会让你的代码变得非常有趣。如果性能不是主要问题，我会采用下面的列表方法。

您可以使用单个列表<>与斜率和计数相关联的类型，类似于：

class SlopeCount
{
    public int Slope { get; set; }
    public int Count { get; set; }
}

然后：

var slopeCounts = new List<SlopeCount>();
// fill the list
相关文章：