2

我目前正在尝试验证，给定一个长度为 N 的未排序数组 A 和一个整数 k，是否存在一些出现 n/k 次或更多次的元素。

我对这个问题的想法是计算模式，然后将其与 n/k 进行比较。但是，我不知道如何快速计算这种模式。我的最终结果需要是 n log(k)，但我真的不知道如何做到这一点。我能找到的最快的是n k...

4

5 回答 5

6

使用哈希表计算每个值的频率：

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

int mostFrequent;
uint maxCount = 0;
foreach(num, count; counts) {
    if(count > maxCount) { 
        mostFrequent = num;
        maxCount = count;
    }
}
于 2009-02-04T18:15:29.930 回答
2

设置 m = n/k 向上取整。进行快速排序，但丢弃长度小于 m 的子列表。

像快速排序一样，你可能运气不好，反复选择接近末端的枢轴。但是，如果您随机选择枢轴，这发生的可能性很小。

递归将有 O(log(k)) 个级别，每个级别需要 O(n) 时间。

于 2009-02-04T22:09:50.177 回答
1

只需遍历数组并将计数保存在哈希/字典中（一旦找到 n/k 就返回 true，否则返回 false）将是 O(n)

编辑，类似于：

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
于 2009-02-04T18:16:47.213 回答
1

在 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;;`

于 2012-10-19T07:48:12.237 回答
0

伪代码：

 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)

于 2009-02-04T18:26:13.093 回答