algorithm - 时间复杂度 - O(n^2) 到 O(n log n) 搜索

Question

我有一个 n 项目的无序列表，我试图在该列表中找到最频繁出现的项目。我写了下面的代码:

def findFrequant(L):
     count = int()
     half = len(L)//2
     for i in L:
          for j in L:
               if i == j:
                    count += 1
                    if count > half:
                         msg = "The majority vote is {0}".format(i)
                         return msg
               else:
                    continue
          count = 0
     return "mixed list!"

显然，这个包含两个循环的过程是 O(n^2)，而我试图在 O(n log n) 时间内完成相同的任务.我不是在寻找修复程序或有人为我编写代码，我只是在寻找方向。

Answer 1

我不认识这里的语言，所以我将其视为伪代码。

这取决于一个哈希表，其键为 L 的相同类型元素，值类型为 int。对哈希表中的每条记录进行计数，然后将哈希表作为普通的键值对集合进行迭代，应用普通的最大列表算法。

O(n) 比线性稍差。我们记得，好的哈希的开销不是线性的，但可以近似为线性的。使用的线性空间。

def findFrequant(L):
     hash = [,]
     vc = 0
     vv = null
     for i in L
         if hash.contains(i)
             hash[i] = hash[i] + 1
         else
             hash[i] = 1
     for (k,v) in hash
         if v > vc
             vv = k
             vc = v
         else if v == vc
             vv = null
     if (vv == null)
         return "mixed list!"
     else
         return "The majority vote is {0}".format(v)