Наименьшее значение в диапазоне
Я хотел бы найти самое низкое значение в некотором диапазоне.
Нужно ли повторять массив каждый раз или есть какой-нибудь динамический метод?
Допустим, у меня есть входной массив:
index: 0 1 2 3 4 5 6 7
value: 1 4 6 1 6 7 2 3
и тогда я должен выбрать самый маленький в диапазоне < а, б> (включительно). Например:
min(0,7) = 1
min(0,2) = 1
min(4,6) = 2
min(1,2) = 4
Меня интересует самое быстрое решение, было бы лучше всего получать результаты в постоянное время.
Массив не будет изменен.
Решение
Если вы собираетесь выполнять несколько запросов по одному и тому же набору чисел, вам нужно создать Декартово дерево.
Декартовы деревья могут использоваться как часть эффективной структуры данных для запросов с минимальным диапазоном, проблема поиска диапазона, включающая запросы, которые запрашивают минимальное значение в смежной подпоследовательности исходной последовательности.
Как говорится в статье, запросы могут выполняться в постоянное время.
Другие решения
Ты можешь использовать сегментное дерево на этот вопрос. это является одним из лучших учебников по дереву сегментов и минимальному диапазону запроса.
Я даю реализацию JAVA, и код не требует пояснений, пожалуйста, дайте мне знать, если у вас есть какие-либо сомнения.
public class SegmentTree {
private int[] array;
private int length;
public static SegmentTree initialize(int[] a) {
return new SegmentTree(a);
}
private SegmentTree(int[] a) {
length = a.length - 1;
int l = (int) (Math.log(a.length) / Math.log(2));
l = (int) (Math.pow(2, l + 1) * 2 - 1);
array = new int[l];
initialize(a, 0, a.length - 1, 0);
}
private int initialize(int[] a, int p, int r, int index) {
if (p == r) {
array[index] = a[p];
return a[p];
}
int q = p + (r - p) / 2;
array[index] = Math.min(initialize(a, p, q, 2 * index + 1), initialize(a, q + 1, r, 2 * index + 2));
return array[index];
}
public int findMin(int p, int r) {
return _findMin(p, r, 0, length, 0);
}
private int _findMin(int qs, int qe, int ss, int se, int i) {
if (qs <= ss && se <= qe) {
return array[i];
}
if (qs > se || qe < ss) {
return Integer.MAX_VALUE;
}
int q = ss + (se - ss) / 2;
return Math.min(_findMin(qs, qe, ss, q, 2 * i + 1), _findMin(qs, qe, q + 1, se, 2 * i + 2));
}
private void print() {
int index = 0;
for (int k : array) {
System.out.println(index + ":" + k);
index++;
}
}
public static void main(String[] args) {
int[] a = {1, 34, 5, 6, 78, 5, 67, 89};
SegmentTree s = initialize(a);
System.out.println(s.findMin(2, 4));
}
}
Вы можете попробовать следующее (не уверен, что я что-то упустил)
Если вам разрешена некоторая предварительная обработка, то вы можете иметь массив локальных минимумов (долин).
Этот массив должен быть отсортирован по соответствующим индексам.
Как только вы получите интервал, выполните бинарный поиск по нижнему индексу в массиве минимумов. Выберите больший в этом массиве. скажи I1
Затем выполните бинарный поиск более высокого заданного индекса в массиве минимумов. Выберите меньший в этом массиве. скажи I2
Если I2> = I1, то хотя бы один локальный минимум существует в интервале. Просто сравните значения в минимумах в этом интервале и на границах чтобы получить ответ.
Иначе, локальный минимум не существует в интервале. В этом случае минимум должен быть на границе интервала. Просто сравните два значения и получите нижнее.
Это стандартная задача. Вы можете использовать функциональность библиотеки std. Это должно быть максимально быстро. Пример из Вот:
#include <iostream> // std::cout
#include <algorithm> // std::min_element, std::max_element
int main () {
int myints[] = {3,7,2,5,6,4,9};
std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';
return 0;
}
Постскриптум Вы не можете получить результат в постоянное время, так как если вам нужно минимум между N элементами, вам нужно проверить каждый элемент. Минимальная сложность задачи O (N).