候鸟溶液

Question

我为这个实践在HackerRank上编写了这个解决方案，但是它不能处理“由于超时而终止”的大数据。我将在这里包括问题的描述。

你被要求帮助研究在大陆上迁徙的鸟类的数量。您感兴趣的每一种鸟都将被一个整数值所识别。每次发现一种特定的鸟，它的id号就会被添加到你的目击记录中。你会想要找出哪种鸟是最常见的，给出一张目击名单。您的任务是打印该鸟类的类型号，如果两个或多个类型的鸟类相同，则选择ID号最小的类型。 例如，假设你的鸟类目击事件是arr=1,1,2,2,3类型，1型和2型各有两种，3型有一种，选择两种类型中较低的一种:1型。 职能说明： 在下面的编辑器中完成migratoryBirds函数。它应该返回最常见鸟类的最低类型数。migratoryBirds具有以下参数： arr:一组表示可见鸟类类型的整数。 输入格式 第一行包含一个整数，表示n，即数组arr中看到和报告的鸟类数量。 第二行将arr描述为n个空格分隔的整数，表示每一个可见鸟的类型数。 约束条件 5 <= n <= 2 X 10^5 保证每种类型为1、2、3、4或5。

我的代码如下。

    result=" "
    for i in arr:
        for j in arr:
            if arr.count(i)>=2 and arr.count(j)<2:
                result=i


            elif arr.count(i)==arr.count(j)>=2 and j<i:
                result=j         

   print(result)     

我该如何改进呢？

Answer 1

由于代码的复杂性为O(n^3)，您的代码会遇到超时错误。

要通过测试，您需要一个O(n)算法，它可以实现如下所示。

准备一个长度为5的列表，用所有的0开始。我们将使用这个列表来计算每种鸟类的数量。如果你愿意的话，用字典也可以。

现在，运行输入数组并增加计数。也就是说，如果遇到类型i，则将(i-1)-th条目增加为1。

现在查找最大计数并返回相应的索引+ 1。

def migratoryBirds(arr):
    typecount = [0 for i in range(5)]
    for i in arr:
        typecount[i-1] += 1
    max_count = max(typecount)
    for i in range(5):
        if typecount[i] == max_count:
            return i+1

Answer 2

你可以用collections.Counter来做这件事

from collections import Counter


a = [int(e) for e in "1 2 3 4 5 4 3 2 1 3 4".split(' ')]
c = Counter(a).most_common()
print(sorted([elt for elt in c if elt[1] == c[0][1]])[0][0])

Answer 3

您的代码由于时间复杂性o(n3)而超时。

from collections import Counter
    def migratoryBirds(arr):
        arr.sort()
        result=Counter(arr)
        return(max(result, key=result.get))

首先，您需要对数组进行排序，并使用计数器来计数元素，并使用max函数可以得到所需的no。