利用连接计数数组在数组中查找索引项的有效方法
我有一个包含两个数组的对象，第一个是斜率数组：
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 }是否有更好的方法在坡度中查找i_th项，而不是使用索引遍历Counts并在Slopes中找到相应的索引
编辑:不确定是不是我的问题不清楚。我需要能够访问发生的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];
}我想知道有没有更有效的方法？
回答 6
Stack Overflow用户
发布于 2012-02-03 00:54:26
您可以使用第三个数组来存储重复坡度的第一个索引
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(log(n))，而不是O(n)。
Stack Overflow用户
发布于 2012-02-03 00:52:26
如果您一次加载坡度并执行许多这样的“第i项”查找，那么使用包含总计的第三个(或不是计数，取决于用于什么)数组可能会有所帮助。对于您的示例，这将是{ 0, 3, 4, 5 }。然后你不需要在每次查找时将它们相加，这只是一个“我是否在Totalsx和Totalsx +1之间”的问题。如果你希望有几个坡度桶，或者如果坡度是在处理过程中添加的，或者如果你不做很多这样的查找，那么它可能不会给你带来任何好处。从本质上讲，这只是一次完成所有这些添加。
Stack Overflow用户
发布于 2012-02-03 00:54:57
您总是可以将现有数组和另一个数组(称为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 }https://stackoverflow.com/questions/9115907
复制相似问题
腾讯云开发者
