как вычислить режим несортированного массива целых чисел в O (N)?

Question

... с использованием итеративной процедуры (без хэш-таблицы)?

Это не домашнее задание. И по режиму я имею в виду наиболее частое число (статистический режим). Я не хочу использовать хеш-таблицу, потому что хочу знать, как это можно сделать итеративно.

Answer 1

OK Фантаус, как это можно сделать?

Сортировка списка с помощью алгоритма RadixSort (BucketSort) (технически O (N) время, цифры должны быть целыми). Начните с первого элемента, запомните его значение и запустите счет в 1. Перейдите в список, увеличивая счет, пока не достигнете другого значения. Если счетчик для этого значения больше текущего текущего счета, помните это значение и считайте его как режим. Помните оба (или все) номера, если вы получите галстук с высоким счетом.

... да, да, RadixSort не является сортировкой на месте и, следовательно, включает в себя что-то, что вы могли бы назвать хэш-таблицей (коллекцией коллекций, индексированной текущей цифрой). Однако хеш-таблица используется для сортировки, а не для вычисления режима.

Я собираюсь сказать, что в несортированном списке было бы невозможно вычислить режим в линейном времени без привлечения хэш-таблицы SOMEWHERE. В отсортированном списке вторая половина этого алгоритма работает, просто отслеживая текущее значение max.

Answer 2

Определенно звучит как домашнее задание. Но попробуйте это: просмотрите список один раз и найдите наибольшее число. Создайте массив целых чисел с таким количеством элементов, все инициализируются до нуля. Затем перейдите в список еще раз, и для каждого числа увеличьте эквивалентный индекс массива на 1. Наконец, сканируйте свой массив и верните индекс, который имеет самое высокое значение. Это будет выполняться примерно в линейном времени, тогда как любой алгоритм, который включает сортировку, вероятно, займет время NlogN или хуже. Тем не менее, это решение - болото памяти; это будет в основном создать колокольчик, чтобы дать вам один номер из него.

Помните, что многие (но не все) языки используют массивы с нулевым значением, поэтому при преобразовании из «натурального» номера в индекс вычитайте один, а затем добавьте один из индекса в натуральное число.

Answer 3

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

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

Answer 4

Просто используйте подсчет сортировки и посмотрите в массив, в котором хранятся номера вхождения для каждого объекта entity.h, чтобы хранить число вхождений для каждого объекта.

Answer 5

я подготовил две реализации в Python с различной пространственной и временной сложности:

Первый из них использует «вхождение массив» представляет собой О (к) с точки зрения времени сложности и S (к + 1) в терминах пространства где k - наибольшее число во входных данных.

input =[1,2,3,8,4,6,1,3,7,9,6,1,9] 

def find_max(tab): 
    max=tab[0] 
    for i in range(0,len(tab)): 
     if tab[i] > max: 
      max=tab[i] 
    return max 

C = [0]*(find_max(input)+1) 
print len(C) 
def count_occurences(tab): 
    max_occurence=C[0] 
    max_occurence_index=0 
    for i in range(0,len(tab)): 
     C[tab[i]]=C[tab[i]]+1 
     if C[tab[i]]>max_occurence: 
      max_occurence = C[tab[i]] 
      max_occurence_index=tab[i] 
    return max_occurence_index 

print count_occurences(input) 

Примечание: Представьте, такой жалкий пример ввода, как массив [1, 10]^8,1,1,1, будет массив длины к + 1 = 100000001 необходимо.

Второе решение предполагает, что мы сортируем наш вход перед поиском режима. Я использовал сортировку radix, которая имеет временную сложность O (kn), где k - длина самого длинного числа, а n - размер входного массива. И тогда нам придется перебирать весь отсортированный массив размером n, чтобы определить самое длинное подмножество чисел, стоящих для режима.

input =[1,2,3,8,4,6,1,3,7,9,6,1,9] 

def radix_sort(A): 
    len_A = len(A) 
    mod = 5 #init num of buckets 
    div = 1 
    while True: 
     the_buckets = [[], [], [], [], [], [], [], [], [], []] 
     for value in A: 
      ldigit = value % mod 
      ldigit = ldigit/div 
      the_buckets[ldigit].append(value) 
     mod = mod * 10 
     div = div * 10 
     if len(the_buckets[0]) == len_A: 
      return the_buckets[0] 
     A = [] 
     rd_list_append = A.append 
     for b in the_buckets: 
      for i in b: 
       rd_list_append(i)  

def find_mode_in_sorted(A): 
    mode=A[0] 
    number_of_occurences =1 
    number_of_occurences_canidate=0 
    for i in range(1,len(A)): 
     if A[i] == mode: 
      number_of_occurences =number_of_occurences +1 
     else: 
      number_of_occurences_canidate=number_of_occurences_canidate+1 
     if A[i] != A[i-1]: 
      number_of_occurences_canidate=0 
     if number_of_occurences_canidate > number_of_occurences : 
      mode=A[i] 
      number_of_occurences =number_of_occurences_canidate+1 
    return mode#,number_of_occurences 

s_input=radix_sort(input) 
print find_mode_in_sorted(s_input) 

Answer 6

Этот код использует цикл для вычисления режима элемента (наиболее часто) и работает время O (N)

int find(int* arr, int size) { 
    int count = 0, i, me; 
    for (i = 0; i < size; i++) { 
     if (count == 0) 
      me = arr[i]; 
     if (arr[i] == me) 
      count++; 
     else 
      count--; 
    } 
    return me; 
} 

Answer 7

Использование JavaScript:

const mode = (arr) => { 
    let numMapping = {}; 
    let mode 
    let greatestFreq = 0; 
    for(var i = 0; i < arr.length; i++){ 
     if(numMapping[arr[i]] === undefined){ 
      numMapping[arr[i]] = 0; 
     } 
     numMapping[arr[i]] += 1; 
     if (numMapping[arr[i]] > greatestFreq){ 
      greatestFreq = numMapping[arr[i]] 
      mode = arr[i] 
     } 
    } 
    return parseInt(mode) 
}