Actually my previous algorithm can be modified to get all the maxima in O(log n) time. I tested that it works great for all the input provided. Please let me know your feedback
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("nn");
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;
}
}
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <time.h> #include <stdio.h> #include <locale.h> #include <stdlib.h> #define WINDOWS "russian" #define LINUX "ru_RU.UTF-8" char * result_str (int); void random_arr (int *, int); void printf_arr (int *, int); int local_check (int *, int, int); int count_min (int *, int, int); int countLocalMin (int *, int, int); int main (void) { setlocale(LC_ALL, LINUX); srand( (unsigned int)time(NULL)/2 ); int size, a[100]; printf("Введите размер массива: "); if (scanf("%d", &size) != 1 || size < 1 || size > 100) return 1; puts(""); random_arr(a, size); // заполняем массив случайными printf_arr(a, size); // выводим его на экран puts("n"); // int delta = 1; // для теста int delta = 1 + rand() %((size >> 1) - !(size % 2)); int segment = (delta << 1) + 1; printf("Ширина диапазона: %dnn", segment); int cnt; clock_t begin, end; begin = clock(); cnt = count_min(a, size, segment); printf("nПроверка выявила %d %s.n", cnt, result_str(cnt)); end = clock(); printf("Затраченное время: %.8lfnn", (double)(end-begin)/CLOCKS_PER_SEC); begin = clock(); cnt = countLocalMin(a, size, delta); printf("nПроверка выявила %d %s.n", cnt, result_str(cnt)); end = clock(); printf("Затраченное время: %.8lfnn", (double)(end-begin)/CLOCKS_PER_SEC); return 0; } // ------------------------------------------------------------ char *result_str (int n) { static char str[3][64] = { "локальный минимум", "локальных минимума", "локальных минимумов" }; int result = 0; if (n > 99) return result_str(n % 100); else if (n > 19) return result_str(n % 10); else if (n == 1) result = 0; else if (n > 1 && n < 5) result = 1; else result = 2; return str[result]; } // ------------------------------------------------------------ void random_arr (int *array, int size) { for (int i = 0; i < size; ++i) array[i] = rand() %10; } // ------------------------------------------------------------ void printf_arr (int *array, int size) { for (int i = 0; i < size; ++i) printf("%2d", array[i]); } // ------------------------------------------------------------ int local_check (int *array, int size, int min_pos) { int check = 1; for (int i = 0, k = size-1; i < k && check > 0; ++i, --k) check = (array[i] > array[min_pos] && array[k] > array[min_pos]); return check; } // ------------------------------------------------------------ int count_min (int *array, int size, int segment) { int count = 0; int mid_pos = segment >> 1; // mid_pos = segment / 2 int length = size - segment; for (int i = 0; i <= length; ++i) { int result = local_check(array+i, segment, mid_pos); count += result; // count += local_check(array+i, segment, mid_pos); printf("диапазон:"); // всякие визуальные ненужности printf_arr(array+i, segment); printf(" проверка: %dn", result); } return count; } // ------------------------------------------------------------ // Вариант analogov net int countLocalMin( int *a, int n, int delta ) { int k = 0; int segment = (delta << 1) + 1; // segment = delta*2 + 1 int length = n - delta; for( int i = delta; i < length; ++i ) { int check = 1; for( int n = 1; n <= delta && check > 0; ++n ) if( a[i] >= a[i - n] || a[i] >= a[i + n] ) check = 0; k += check; printf("диапазон:"); // всякие визуальные ненужности printf_arr(a+i-delta, segment); printf(" проверка: %dn", check); } return k; } // ------------------------------------------------------------ |
Две красивые задачи по алгоритмам
Время на прочтение
4 мин
Количество просмотров 67K
На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.
Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.
Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.
Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).
Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.
Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.
Попытаюсь рассказать не только решение, но и то, как до него можно было бы догадаться. Пояснять буду сразу на примере. Из него, надеюсь, будет понятно, как алгоритм работает в общем случае. Рабочий пример:
То есть нам дан массив длины 9, содержащий числа от 1 до 8, и наша цель — найти двойку или пятёрку.
Как мы помним, использовать дополнительную память в условии задачи запрещено. Давайте, однако, поймем, чем она могла бы нам помочь. Мы бы тогда завели новый массив размера n и одним проходом по исходному массиву A посчитали бы, сколько раз каждое из чисел от 1 до n входит в A. По этому массиву было бы сразу видно, кто в A повторяется.
Это в дальнейшем не особо нам поможет, но всё же.
Ограничение на дополнительную память не даёт нам собрать и записать вспомогательную информацию о массиве. Значит, повторяющийся элемент нам нужно найти, как-то «гуляя» по массиву. Гулять по массиву можно слева направо, например, но непонятно, какую информацию можно при этом извлечь. Поэтому попробуем гулять по-другому. Встанем в первый элемент нашего массива и посмотрим, что там написано. Написано там число 7, поэтому давайте посмотрим на седьмой элемент массива. Там записано число 1. Прогулка получилась недолгой, мы зациклились. То, что в массиве есть какие-то циклы, очень нам поможет в дальнейшем. Для примера давайте ещё попробуем прогуляться из второго элемента: оттуда мы пойдём в элемент номер 5, из него — в элемент номер 3, а из элемента номер 3 опять вернёмся обратно в элемент номер 2. То есть нашли ещё один цикл. Давайте изобразим найденные нами два цикла:
И раз уж мы осознали, что наш массив неявно задаёт некоторый граф, то давайте явно этот граф нарисуем. Формально, вершины графа — это числа от 1 до n+1; мы проводим ориентированное ребро из i в j, если A[i]=j.
Интересуют нас в этом графе вершины, в которые входят хотя бы два ребра (если в вершину j входят рёбра из вершин i и k, то A[i]=A[k]=j, то есть j повторяется в массиве A). Нам и так ясно, что такая вершина в графе есть, но давайте это осознаем ещё раз, в терминах графов. В нашем графе из каждой вершины выходит ровно одно ребро (и значит, в графе (n+1) ребро), но есть одна вершина, в которую ничего не входит: это вершина (n+1). Значит, найдётся вершина, в которую входит хотя бы два ребра. В общем-то, это и так было ясно, но вот замечание про вершину (n+1) нам в дальнейшем поможет.
Давайте встанем в вершину (n+1) и будем переходить в нашем графе по исходящим рёбрам. Когда-нибудь мы зациклимся, конечно, но важно то, что мы не вернёмся в вершину (n+1). В нашем рабочем примере мы выйдем из вершины 9 и дойдём до цикла (5,2,3). Видно, что точка входа в этот цикл — это и есть повторяющийся элемент: ведь в эту точку и по ребру цикла можно войти, и по ребру на пути из вершины (n+1) в цикл. В нашем примере такая точка входа — это вершина 5.
Нахождение этой точки — отдельная не слишком простая задача, но её решение очень похоже на решение стандартной задачи о зацикленности списка. Длину цикла найти несложно. Например, сделаем n+1 шаг из вершины n+1. После этого мы обязательно окажемся в вершине на цикле. Запомним эту вершину и будем продолжать шагать, пока не вернёмся в неё. Тем самым узнаем длину цикла k. Теперь сделаем следующее. Поставим два указателя в вершину n+1. Первым указателем сделаем k шагов. После этого будем двигать каждый из указателей на один шаг вперёд, пока они не встретятся (таким образом, первый указатель всегда будет обгонять второй на k шагов). Ясно, что встретятся эти ребята как раз в нужной нам точке входе. В нашем примере длина цикла равна трём. После трёх шагов первый указатель окажется в вершине 2. В этот момент мы начнём двигать и второй указатель. Через два шага указатели встретятся в вершине 5.
На закуску. Мы не обсудили, почему же было запрещено модифицировать массив (и наш алгоритм массив, действительно, не трогал). Придумайте более простое решение, если разрешается портить массив.
Найти локальные минимумы n-мерного массива.
Локальные минимумы определяются как связанные наборы пикселей с одинаковым уровнем серого (плато),строго меньшим,чем уровни серого всех пикселей в окрестности.
- Parameters
-
-
imagendarray
-
n-мерный массив.
-
selemndarray, optional
-
Элемент структурирования, используемый для определения окрестности каждого оцениваемого пикселя (
True
обозначает подключенный пиксель). Это должен быть логический массив и иметь такое же количество измерений, что иimage
. Если не заданы ниselem
ни возможностьconnectivity
, все соседние пиксели считаются частью окрестности. -
connectivityint, optional
-
Число, используемое для определения окрестности каждого оцениваемого пикселя. Соседние пиксели, квадрат расстояния от центра которых меньше или равен
connectivity
, считаются соседями. Игнорируется, еслиselem
не равен None. -
indicesbool, optional
-
Если True, на выходе будет кортеж одномерных массивов, представляющих индексы локальных минимумов в каждом измерении. Если False, на выходе будет логический массив той же формы, что и
image
. -
allow_bordersbool, optional
-
Если true,то плато,которые касаются границы изображения,являются действительными минимумами.
-
- Returns
-
-
minimandarray or tuple[ndarray]
-
Если
indices
имеет значение false, возвращается логический массив той же формы, что иimage
сTrue
, указывающим положение локальных минимумов (в противном случае —False
). Еслиindices
имеет значение true, набор одномерных массивов, содержащий координаты (индексы) всех найденных минимумов.
-
Notes
Эта функция работает на основе следующих идей:
- Сделайте первый проход по последнему измерению изображения и отметьте кандидатов для локальных минимумов, сравнивая пиксели только в одном направлении. Если пиксели не связаны в последнем измерении, вместо этого все пиксели помечаются как кандидаты.
Для каждого кандидата:
- Выполните заливку,чтобы найти все соединенные пиксели,которые имеют одинаковое значение серого цвета и являются частью плато.
- Рассмотрим связную окрестность плато:если ни один из граничащих образцов не имеет меньшего уровня серого,пометьте плато как определенный локальный минимум.
Examples
>>> from skimage.morphology import local_minima >>> image = np.zeros((4, 7), dtype=int) >>> image[1:3, 1:3] = -1 >>> image[3, 0] = -1 >>> image[1:3, 4:6] = -2 >>> image[3, 6] = -3 >>> image array([[ 0, 0, 0, 0, 0, 0, 0], [ 0, -1, -1, 0, -2, -2, 0], [ 0, -1, -1, 0, -2, -2, 0], [-1, 0, 0, 0, 0, 0, -3]])
Найдите локальные минимумы,сравнивая со всеми соседними пикселями (максимальная связность):
>>> local_minima(image) array([[False, False, False, False, False, False, False], [False, True, True, False, False, False, False], [False, True, True, False, False, False, False], [ True, False, False, False, False, False, True]]) >>> local_minima(image, indices=True) (array([1, 1, 2, 2, 3, 3]), array([1, 2, 1, 2, 0, 6]))
Найти локальные минимумы без сравнения с диагональными пикселями (связность 1):
>>> local_minima(image, connectivity=1) array([[False, False, False, False, False, False, False], [False, True, True, False, True, True, False], [False, True, True, False, True, True, False], [ True, False, False, False, False, False, True]])
и исключить минимумы,граничащие с краем изображения:
>>> local_minima(image, connectivity=1, allow_borders=False) array([[False, False, False, False, False, False, False], [False, True, True, False, True, True, False], [False, True, True, False, True, True, False], [False, False, False, False, False, False, False]])
Учитывая массив целых чисел, найдите локальные минимумы. Элемент A [i] определяется как локальный минимум, если A [i-1] > A [i] и A [i] A [i + 1], где я = 1… n-2. В случае граничных элементов число должно быть меньше его соседнего числа.
Я знаю, существует ли только один локальный минимум, тогда мы можем решить с измененным двоичным поиском.
Но если известно, что в массиве существует несколько локальных минимумов, можно ли это решить в O(log n)
времени?
Ответ 1
Если элементы массива не гарантированно отличаются друг от друга, тогда это невозможно сделать в O (log n) времени. Причина этого заключается в следующем: предположим, что у вас есть массив, где все значения n > 1 одинаковы. В этом случае ни один из элементов не может быть локальным минимумом, потому что ни один элемент не меньше его соседей. Однако, чтобы определить, что все значения одинаковы, вам придется посмотреть на все элементы массива, который принимает время O (n). Если вы используете меньше времени O (n), вы не можете обязательно просмотреть все элементы массива.
Если, с другой стороны, элементы массива гарантированно различны, вы можете решить это в O (log n), используя следующие наблюдения:
- Если есть только один элемент, он гарантированно является локальным минимумом.
- Если есть несколько элементов, посмотрите на средний элемент. Если это локальный минимум, все готово. В противном случае, по крайней мере, один из элементов рядом с ним должен быть меньше, чем он. Теперь представьте, что произойдет, если вы начнете с одного из меньших элементов и постепенно переходите к одному из концов массива в направлении от среднего элемента. На каждом шаге либо следующий элемент меньше предыдущего, либо он будет больше. В конце концов, вы либо попадете в конец массива таким образом, либо вы нажмете локальный минимум. Обратите внимание, что это означает, что вы могли сделать это, чтобы найти локальный минимум. Однако мы на самом деле не собираемся это делать. Вместо этого мы будем использовать тот факт, что локальный минимум будет существовать в этой половине массива как оправдание для выброса одной половины массива. В том, что осталось, мы гарантированно найдем локальный минимум.
Следовательно, вы можете создать следующий рекурсивный алгоритм:
- Если есть только один элемент массива, это локальный минимум.
- Если есть два элемента массива, проверьте каждый. Нужно быть локальным минимумом.
- В противном случае посмотрите на средний элемент массива. Если это локальный минимум, верните его. В противном случае, по крайней мере одно соседнее значение должно быть меньше этого. Recurse в половине массива, содержащего этот меньший элемент (но не средний).
Обратите внимание, что это имеет рекуррентное отношение
T (1) & le; 1
T (2) & le; 1
T (n) & le; T (n/2) + 1
Используя основную теорему, вы можете показать, что этот алгоритм работает по времени O (log n), если требуется.
Надеюсь, это поможет!
Также обратите внимание, что этот алгоритм работает только в том случае, если ребра массива считаются локальными минимумами, если они меньше смежного элемента.
Ответ 2
Число локальных минимумов может быть n/2
; вы не можете перечислить их всех в O(log n)
времени.
Ответ 3
Используйте алгоритм разделения и покоя. Пусть 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).
Ответ 4
Алгоритм не будет работать для этого массива
15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1
Здесь локальные минимумы равны 12.. но когда я проверяю средний элемент, который равен 7, алгоритм отбрасывает левую половину (которая имеет минимумы) и проверяет правильную половину. Следовательно, это не работает.
Я думаю, что это будет работать только для специального случая, когда массив обладает специальным свойством: A [1] ≥ A [2] и
A [n — 1] ≤ A [n].
Ответ 5
Оригинальный вопрос не является полным.
Просто нашел полный вопрос и подробное объяснение в
Найти локальные минимумы в массиве! — не мой блог
Учитывая массив уникальных целых чисел, чьи первые два числа уменьшаются, а последние два числа увеличиваются, найдите число в массиве, которое является локальным минимумом. Число в массиве называется локальным минимумом, если оно меньше, чем его левое и правое числа.
Например, в массиве 9,7,2,8,5,6,3,4
2 является локальным минимумом, так как он меньше его левого и правого числа 7 и 8. Аналогично, 5 — это еще один локальный минимум, поскольку он находится между 8 и 6, как больше 5.
Вам нужно найти любой из локальных минимумов.
Ответ 6
Вот решение, которое работает на 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;
}
}
}
Ответ 7
На самом деле мой предыдущий алгоритм можно изменить, чтобы получить все максимумы в 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("nn");
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;
}
}
}
}