Учитывая массив целых чисел, найдите локальные минимумы. Элемент A [i] определяется как локальный минимум, если A [i-1] > A [i] и A [i] A [i + 1], где я = 1... n-2. В случае граничных элементов число должно быть меньше его соседнего числа.
Я знаю, существует ли только один локальный минимум, тогда мы можем решить с измененным двоичным поиском.
Но если известно, что в массиве существует несколько локальных минимумов, можно ли это решить в O(log n) времени?
Если элементы массива не гарантированно отличаются друг от друга, тогда это невозможно сделать в O (log n) времени. Причина этого заключается в следующем: предположим, что у вас есть массив, где все значения n > 1 одинаковы. В этом случае ни один из элементов не может быть локальным минимумом, потому что ни один элемент не меньше его соседей. Однако, чтобы определить, что все значения одинаковы, вам придется посмотреть на все элементы массива, который принимает время O (n). Если вы используете меньше времени O (n), вы не можете обязательно просмотреть все элементы массива.
Если, с другой стороны, элементы массива гарантированно различны, вы можете решить это в O (log n), используя следующие наблюдения:
Следовательно, вы можете создать следующий рекурсивный алгоритм:
Обратите внимание, что это имеет рекуррентное отношение
T (1) & le; 1
T (2) & le; 1
T (n) & le; T (n/2) + 1
Используя основную теорему, вы можете показать, что этот алгоритм работает по времени O (log n), если требуется.
Надеюсь, это поможет!
Также обратите внимание, что этот алгоритм работает только в том случае, если ребра массива считаются локальными минимумами, если они меньше смежного элемента.
Число локальных минимумов может быть n/2; вы не можете перечислить их всех в O(log n) времени.
Используйте алгоритм разделения и покоя. Пусть m = n/2 и рассмотрим значение A [m] (что is, элемент в середине массива).
Случай 1: A [m-1] А [м]. Тогда левая половина массива должна содержать локальный минимум, поэтому рекурсия в левой половине. Мы можем показать это противоречием: предположим, что A [i] не является локальным минимумом для каждого 0 ≤ я < м. Тогда A [m-1] не является локальным минимумом, откуда следует, что A [m-2] А [м-1]. Аналогично, A [m -3] A [м -2]. Продолжая таким образом, получаем A [0] А [1]. Но тогда A [0] является локальным минимумом, вопреки нашему начальному предположению.
Случай 2: A [m + 1] > A [m]. Тогда правая половина массива должна содержать локальный минимум, поэтому рекурсия в правой половине. Это симметрично случаю 1.
Случай 3: A [m - 1] > A [m] и A [m + 1] А [м]. Тогда A [m] является локальным минимумом, поэтому вернем его. Рекуррентное время работы T (n) = T (n/2) + Θ (1), что дает T (n) = Θ (log n).
Алгоритм не будет работать для этого массива
15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1
Здесь локальные минимумы равны 12.. но когда я проверяю средний элемент, который равен 7, алгоритм отбрасывает левую половину (которая имеет минимумы) и проверяет правильную половину. Следовательно, это не работает.
Я думаю, что это будет работать только для специального случая, когда массив обладает специальным свойством: A [1] ≥ A [2] и A [n - 1] ≤ A [n].
Оригинальный вопрос не является полным.
Просто нашел полный вопрос и подробное объяснение в Найти локальные минимумы в массиве! - не мой блог
Учитывая массив уникальных целых чисел, чьи первые два числа уменьшаются, а последние два числа увеличиваются, найдите число в массиве, которое является локальным минимумом. Число в массиве называется локальным минимумом, если оно меньше, чем его левое и правое числа.
Например, в массиве 9,7,2,8,5,6,3,4 2 является локальным минимумом, так как он меньше его левого и правого числа 7 и 8. Аналогично, 5 - это еще один локальный минимум, поскольку он находится между 8 и 6, как больше 5.
Вам нужно найти любой из локальных минимумов.
Вот решение, которое работает на O (log n). В принципе, это работает на подходе сортировки слияния (разделяй и властвуй).
public class LocalMaxima {
int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59};
@Test
public void localMaxima () {
System.out.println((a[localMaxima(0,a.length-1)]));
}
int localMaxima(int low, int high) {
if(high-low > 2) {
int mid = (low+high)/2;
return maxof(localMaxima(low,mid),localMaxima(mid+1, high));
}
else if(high-low == 1) {
return maxof(high,low);
}
else if(high-low == 0) {
return high;
}
if(high-low == 2) {
return maxof(maxof(low, high),low+1);
}
return 0;
}
int maxof(int i, int j) {
if(a[i] <a[j]) {
return j;
}
else {
return i;
}
}
}
На самом деле мой предыдущий алгоритм можно изменить, чтобы получить все максимумы в O (log n). Я тестировал, что он отлично работает для всех предоставленных материалов. Пожалуйста, дайте мне знать ваши отзывы.
public class LocalMaximas {
@Test
public void test () {
System.out.println("maximas: please modify code to handle if array size is <= 2");
int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59,2};
localMaximas(a);
int []b = {9,7,2,8,5,6,3,4, 2}; //9,8,6,4
localMaximas(b);
int [] c= {15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1};//15,20
localMaximas(c);
}
public void localMaximas (int [] a) {
System.out.println("\n\n");
if(isMaxima(a,0)) {
System.out.println(a[0]);
}
if(isMaxima(a,a.length-1)) {
System.out.println(a[a.length-1]);
}
localMaximas(a,0,a.length-1);
}
int localMaximas(int []a,int low, int high) {
int mid = (low+high)/2;
if(high-low > 3) { // more than 4 items in currently divided array
if(isMaxima(a,mid)) {
System.out.println(a[mid]);
}
localMaximas(a,low, mid);
localMaximas(a,mid, high);
}
else if(high-low == 3){ //exactly 4 items in currently divided array
localMaximas(a,low, mid+1);
localMaximas(a,mid, high);
}
else if((high-low == 2) && (isMaxima(a,low+1))) {
System.out.println(a[low+1]);
}
return 0;
}
int maxof(int []a, int i, int j) {
if(a[i] <a[j]) {
return j;
}
else {
return i;
}
}
boolean isMaxima(int []a ,int mid) {
if(mid == 0) {
if(maxof(a, mid, mid+1) == mid) {
return true;
}
else {
return false;
}
}
else if(mid==a.length-1) {
if(maxof(a,mid,mid-1) == mid) {
return true;
}
else {
return false;
}
}
else {
if((maxof(a, mid, mid+1) == mid) && (maxof(a, mid, mid-1) == mid)) {
return true;
}
else {
return false;
}
}
}
}