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

Если вы собираетесь делать это много, вы можете повысить производительность, отслеживая максимумы / минимумы в разных масштабах.

Например, если вы ведете список для каждых 20 строк и хотите проверить диапазон 55–184, вам нужно будет проверить только 5 значений (55–59), затем 6 значений из 60–179, затем 4 значения от 180 до 184, то есть 15 проверок, а не 130, увеличение скорости в 20 раз.

Конечно, вам нужно помечать ваши сегменты как измененные при изменении массива и периодически обновлять их.

Answer 4

Иметь цикл, который проходит по выбранному подразделу один раз.

В цикле настройте значения четырех переменных maxValue, maxIndex, minValue, minIndex, когда вы найдете новые максимумы или минимумы.

После цикла у вас будет максимум и минимум и их позиции.

Никакой дополнительной памяти не требуется, линейная производительность (всего один проход по выбранной части массива).