Вычисление статистического режима

Question

В настоящее время я пытаюсь проверить, не задан ли несортированный массив A длины N и целое число k, существует ли какой-либо элемент, который имеет место n/k раз или больше.

Мое мышление для этой проблемы состояло в том, чтобы вычислить режим, а затем сравнить это с n/k. Однако я не знаю, как быстро вычислить этот режим. Мой конечный результат должен быть n log (k), но я понятия не имею, как это сделать. Кратчайший я смог найти п к ...

Answer 1

Используйте хэш-таблицу для подсчета частоты каждого значения:

uint[int] counts; 
foreach(num; myArray) { 
    counts[num]++; 
} 

int mostFrequent; 
uint maxCount = 0; 
foreach(num, count; counts) { 
    if(count > maxCount) { 
     mostFrequent = num; 
     maxCount = count; 
    } 
} 

Answer 2

Просто ходить массив и держа отсчеты в хэш/словаря (и возвращение правда один раз п/к находится, иначе ложь) будет O (п)

редактировать что-то вроде:

counts = {} 
for n in numbers: 
    if (counts.has_key(n)): 
     counts[ n ] += 1 
    else: 
     counts[ n ] = 1 
    if (counts[ n ] >= n/k): 
     return true 
return false 

Answer 3

псевдокод:

found = false 
value = null 
B = new hashtable 
for (i =0, j = A[i]; i < |A| and !found; ++i, j=A[i]) 
    if B contains key j 
     B[j] = B[j] + 1 
     if B[j] > |A|/k 
      found = true 
      value = j 
     endif 
    else 
     B[j] = 1 
    endif 
end for 

Предполагая, что ваш Хеш реализация имеет O (1) вставки/поиск это должно быть O (N)

Answer 4

множество М = п/к округляется. Сделайте quicksort, но отбрасывайте подсписные буквы длиной меньше m.

Как быстрая сортировка, вы можете иметь несчастье и многократно выбирать опорные точки, близкие к концам. Но это маловероятно, если вы произвольно выбираете шарниры.

В рекурсии будут уровни O (log (k)), и каждый уровень будет принимать O (n) время.

Answer 5

Расчет статистического режима в F # .net для набора данных (целые числа), который имеет единственный режим

let foundX (num: int, dList) = List.filter (fun x -> x = num) dList 
let groupNum dList = 
    dList 
    |> (List.map (fun x -> foundX (x, dList))) 
    |> (List.maxBy (fun x -> x.Length)) 

let Mode (dList: int List) = 
    let x = groupNum dList 
    x.Head 

//using Mode 
let data = [1;1;1;1;1;1;1;1;2;2;3;3;3;1;4;4;4;4;4] 
Mode data;;`