Найти доминирующий режим несортированного массива

если какое-то число встречается больше половины, это можно сделать с временной сложностью 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;
        }
    }
}

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

Если вы хотите найти только доминирующий режим массива и сделать это рекурсивно, вот псевдокод:

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).