Codility OddOccurrencesInArray in Python

发表于 更新于 分类于 ， Disqus：

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(K)
平均 O(N) O(K)
最差 O(N) O(K)

其中，K是数组中互不相同数的个数

算法分析

遍历数组，算出每个数出现的次数。如果出现的次数为奇数，则返回该数。要点是选择用于记录不同数出现次数的计数器的数据结构和计数方法。对于计数器的数据结构，python built-in的字典可以满足O(1)的读取和记录。对于计数方法，则不必详细记录出现次数，标记奇偶即可。在特定条件下，应该也可以使用位操作，利用二进制0，1比特来标记奇偶，以便使用更小的内存空间。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
def solution(A):
    # write your code in Python 2.7
    count = {}
    for num in A:
        if num in count:
            count[num] = (count[num] + 1) % 2
        else:
            count[num] = 1

    for k in count:
        if count[k] == 1:
            return int(k)