2

我有一个大数组。我有一些 Java 代码用于识别该大数组的子集/切片的起点和终点的索引。我需要从数组的选定子部分检索的唯一信息项是局部最大值和最小值的索引和值。我可以在指定范围内找到最大值和最小值的最快（且内存占用最少）的方法是什么？

这是我在代码方面需要的开始：

// Step One: declare new array and populate it
pts = new double[5000];
for (int i = 0; i < 5000; i++){ pts[i] = (value assigned by extraneous process);}
// Step Two: slice out section between indices 3600 and 3750
    // what code do I write here?
// Step Three: find max value in the sliced section and return its index
    // what code to I write here?
4

4 回答 4

4

只需遍历所需范围并记录最大和最小可见值：

double max = Double.NEGATIVE_INFINITY;
double min = Double.POSITIVE_INFINITY;
int minIndex = -1;
int maxIndex = -1;
for(int k = 3600; k < 3750; k++){
    if(max < pts[k]){
        max = pts[k];
        maxIndex = k;
    }else if(min > pts[k]){
        min = pts[k];
        minIndex = k;
    }
}
于 2011-07-07T02:03:11.247 回答
3

如果不需要为您的切片创建数组的副本，您基本上可以一口气完成第 2 步和第 3 步：

double max = pts[3600]; //the value of the first element in the slice
int maxIndex = 3600; //keep track of the index as you go. Assume at first
                     //that it is the first index of the slice
for(int i=3601; i<=3750; i++){
  if(pts[i] > max){  //you have encountered a larger element. Update the maxes
    max = pts[i];
    maxIndex = i;
  }
}
System.out.println("The max is " + max + " and occurred at index " + maxIndex);

（抱歉有任何语法错误，我一直在搞乱Scala，语法有点不同）

于 2011-07-07T02:02:21.777 回答
1

有一个循环遍历选定的小节一次。

在循环中，当您找到新的最大值或最小值时，调整四个变量maxValue、maxIndex、的值。minValueminIndex

循环之后，您将获得最大值和最小值及其位置。

不需要额外的内存，线性性能（只需遍历数组的选定部分）。

于 2011-07-07T02:02:48.227 回答
1

如果您要经常这样做，您可以通过跟踪不同比例的最大值/最小值来提高性能。

例如，如果您为每 20 行保留一个列表，并且要检查范围 55 - 184，则只需检查 5 个值 (55-59)，然后检查 60-179 中的 6 个值，然后检查 4 个值180 - 184，所以这是 15 次检查而不是 130 次，速度提高了 20 倍。

当然，您需要在数组更改时将存储桶标记为已更改并定期更新它们。

于 2011-07-07T02:44:59.020 回答