Самый большой элемент в массиве Разделяй и властвуй O (N.log (N))

Вот реализация Python, которая подходит под описание (извините, я не разбираюсь в C, но я думаю, что это довольно простой код). Мы можем следить за зарегистрированными возвращаемыми значениями и индексами для каждого проверяемого раздела, чтобы понять, как это работает.

# Returns v if v is a majority;
# otherwise, returns None
def f(arr, low, high):
  if low == high:
    return arr[low]

  if low + 1 == high:
    return arr[low] if arr[low] == arr[high] else None

  n = high - low + 1
  mid = (low + high) / 2

  l = f(arr, low, mid)
  r = f(arr, mid + 1, high)

  print 'n: ' + str(n) + '; l: ' + str(l) + '; r: ' + str(r) + '; L: ' + str((low, mid)) + '; R: ' + str((mid + 1, high))

  if l == r:
    return l

  counts = [0, 0]

  for i in xrange(low, high + 1):
    if arr[i] == l:
      counts[0] = counts[0] + 1
    if arr[i] == r:
      counts[1] = counts[1] + 1

  if l and counts[0] * 2 > n:
    return l

  if r and counts[1] * 2 > n:
    return r

  return None

Вывод:

a = [5, 9, 3, 5, 5, 21, 5, 7, 17, 5, 5, 5]

print f(a, 0, len(a) - 1)

"""
n: 3; l: None; r: 3; L: (0, 1); R: (2, 2)
n: 3; l: 5; r: 21; L: (3, 4); R: (5, 5)
n: 6; l: None; r: 5; L: (0, 2); R: (3, 5)
n: 3; l: None; r: 17; L: (6, 7); R: (8, 8)
n: 3; l: 5; r: 5; L: (9, 10); R: (11, 11)
n: 6; l: None; r: 5; L: (6, 8); R: (9, 11)
n: 12; l: None; r: 5; L: (0, 5); R: (6, 11)
5
"""

Я думаю, что функция должна:

1) Рекурсивно вызывать себя для первой половины массива (возвращает ответ a)

2) Рекурсивно вызывать себя для второй половины массива (возвращает ответ b)

3) Прокрутите массив и подсчитайте, сколько совпадений a/b, и верните тот, который имеет наибольшее количество совпадений.

Обратите внимание, что нет необходимости фактически копировать массив на любом этапе, потому что он никогда не изменяется, просто передайте индекс для начала и длины подмассива.

Вероятно, это не тот ответ, который вы ищете. Но есть интересный вероятностный подход к этой проблеме. Вы можете выбрать определенную позицию x в массиве и подсчитать количество вхождений массива [x], чтобы проверить, появился ли он >= array.size() / 2.

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

Таким образом, если вы делаете что-то вроде 30 итераций, вероятность выбора «доминирующего» элемента составляет (1 - (1/2) ^ 30), что подходит почти для любого приложения.

Сложность O (число итераций * размер массива)

Вот код (:.

Он написан на C++, но могу поспорить, что вы без особых усилий сможете перевести его на C.

#include <vector>
#include <iostream>


int arraySize, numberOfIterations;

int count(int element, std::vector<int>& array)
{
    int count = 0;
    for(const int& number : array)
    {
        count += (number == element);
    }
    return count;
}


int main(){

    srand(time(0));

    std::cin >> arraySize;
    std::vector<int> arr(arraySize);

    for(int i = 0; i < arraySize; ++i)
    {
        std::cin >> arr[i];
    }

    std::cin >> numberOfIterations;

    for(int i = 0; i < numberOfIterations; ++i)
    {
        int idx = rand() % arraySize;
        int freq = count(arr[idx], arr);
        //std::cout << idx << std::endl;
        if(freq > arraySize / 2)
        {
            std::cout << "The element = " << arr[idx] << " dominates the array provided " << std::endl;
            return 0;
        }
    }
    return 0;
}