Найти доминантный режим несортированного массива
Обратите внимание, это домашнее задание.
Мне нужно найти режим массива (положительные значения) и вторично вернуть это значение, если режим больше, чем sizeof(array)/2Доминирующая ценность. Некоторые массивы не будут иметь ни того, ни другого.
Это достаточно просто, но есть ограничение, что массив НЕ должен сортироваться до определения, кроме того, сложность должна быть порядка O (nlogn).
Используя это второе ограничение, и основная теорема мы можем определить, что временная сложность ‘T (n) = A * T (n / B) + n ^ D’, где A = B и log_B (A) = D для O (nlogn), чтобы быть истинной. Таким образом, A = B = D = 2. Это также удобно, поскольку доминантное значение должно быть доминантным в 1-й, 2-й или в обеих половинах массива.
Используя ‘T (n) = A * T (n / B) + n ^ D’, мы знаем, что функция поиска будет вызывать себя дважды на каждом уровне (A), разделив задачу, установленную на 2, на каждом уровне (B). Я застрял, пытаясь понять, как заставить мой алгоритм учитывать n ^ 2 на каждом уровне.
Чтобы сделать некоторый код этого:
int search(a,b) {
search(a, a+(b-a)/2);
search(a+(b-a)/2+1, b);
}
«Клей», который мне здесь не хватает, заключается в том, как объединить эти разделенные функции, и я думаю, что это реализует сложность n ^ 2. Здесь есть какой-то трюк, когда доминант должен быть доминантным в 1-й или 2-й половине или в обоих, не совсем уверен, как это мне сейчас помогает с ограничением сложности.
Я записал несколько примеров небольших массивов и обрисовал, как они будут делиться. Я не могу идти в правильном направлении, чтобы найти один, единственный метод, который всегда будет возвращать доминирующее значение.
На уровне 0 функция должна вызывать себя для поиска первой половины и второй половины массива. То, что нужно рецидивировать и называть себя. Затем на каждом уровне необходимо выполнить n ^ 2 операций. Таким образом, в массиве [2,0,2,0,2] он разделит это на поиск по [2,0] и поиск по [2,0,2] И выполнит 25 операций. Поиск по [2,0] вызовет поиск по [2] и поиск по [0] И выполнит 4 операции. Я предполагаю, что это должен быть поиск самого пространства массива. Я планировал использовать C ++ и использовать что-то из STL для итерации и подсчета значений. Я мог бы создать большой массив и просто обновить счетчики по их индексу.
Решение
если какое-то число встречается более чем наполовину, это может быть сделано за O (n) сложность времени и O (1) сложность пространства следующим образом:
int num = a[0], occ = 1;
for (int i=1; i<n; i++) {
if (a[i] == num) occ++;
else {
occ--;
if (occ < 0) {
num = a[i];
occ = 1;
}
}
}
Поскольку вы не уверены, встречается ли такое число, все, что вам нужно сделать, — это применить вышеупомянутый алгоритм, чтобы сначала получить число, а затем выполнить итерацию всего массива во второй раз, чтобы получить вхождение числа и проверить, больше ли оно половины.
Другие решения
Если вы хотите найти только доминирующий режим массива и сделать это рекурсивно, вот псевдокод:
def DominantMode(array):
# if there is only one element, that's the dominant mode
if len(array) == 1: return array[0]
# otherwise, find the dominant mode of the left and right halves
left = DominantMode(array[0:len(array)/2])
right = DominantMode(array[len(array)/2:len(array)])
# if both sides have the same dominant mode, the whole array has that mode
if left == right: return left
# otherwise, we have to scan the whole array to determine which one wins
leftCount = sum(element == left for element in array)
rightCount = sum(element == right for element in array)
if leftCount > len(array) / 2: return left
if rightCount > len(array) / 2: return right
# if neither wins, just return None
return None
Вышеупомянутый алгоритм O (nlogn) время, но только O (logn) пространство.
Если вы хотите найти режим массива (а не только доминирующий режим), сначала вычислите гистограмму. Вы можете сделать это за O (n) время (посещая каждый элемент массива ровно один раз), сохранив историограмму в хеш-таблице, которая отображает значение элемента на его частоту.
Как только гистограмма будет вычислена, вы можете выполнить итерацию по ней (посещая каждый элемент не более одного раза), чтобы найти самую высокую частоту. Как только вы найдете частоту, превышающую половину размера массива, вы можете сразу же вернуться и игнорировать остальную часть гистограммы. Поскольку размер гистограммы не может быть больше размера исходного массива, этот шаг также составляет O (n) времени (и O (n) пространства).
Поскольку оба шага имеют O (n) время, результирующая алгоритмическая сложность составляет O (n) время.