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

Question

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

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

Answer 1

OK Фантиус, как насчет этого?

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

Использование 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)
}

Answer 5

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

Первая использует «массив вхождений»: O (k) в терминах сложности времени и S (k + 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], будет массивдлины k + 1 = 100000001 необходимо.

Второе решение предполагает, что мы сортируем наш ввод перед поиском режима.Я использовал основную сортировку, которая имеет временную сложность 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

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