hash算法

教材里面使用排序并且去除进行离散化, 本质上是对语言进行映射, 因为语言的编号范围过大了, 无法用数组来计数.
通过离散化, 将语言重新进行编号, 用连续的自然数来编号, 从而缩小语言的编号范围, 方便开数组计数.

这个题解里面不打算这么做, 既然本质上是对语言进行映射, 那为什么不使用hash法呢?
用了Python的Counter, key就是原始的语言编号, value就是语言的个数, 属于具备计数功能的dict.
当然, 还可以自己使用dict, 通过循环, 对各个语言进行计数.

时间复杂度

对科学家语言的计数时间复杂度是O(n)
对电影的语言计数, 时间复杂度是O(m)
总共O(n + m)

Python 代码

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
C = list(map(int, input().split()))

count = Counter(a)

M = 0
Mc = 0
ans = 0
for i, (b, c) in enumerate(zip(B, C), 1):
    b_count = count[b]
    c_count = count[c]
    if (b_count > M) or (b_count == M and c_count > Mc):
        M = b_count
        Mc = c_count
        ans = i
print(ans)