Java：从数组切片中查找最大值的索引

Question

我有一个大数组。我有一些 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?

Answer 1

只需迭代所需的范围并记录最大和最小可见值：

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;
    }
}

Answer 2

如果不需要为切片创建数组的副本，则基本上可以一口气执行步骤 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，语法有点不同）

Answer 3

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

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

循环结束后，您将获得最大值和最小值以及它们的位置。

不需要额外的内存，线性性能（只需一次遍历阵列的选定部分）。

Answer 4

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

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

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