Python算法：求数组中可删除元素的最大数量

给定一个长度为n的数组a，现在有无数次选择，每次选择i,j (i!=j) 并且 a[i]等于a[j]，然后将a[i]至a[j]删除。求能够删除的数最多的是多少？

思路：

使用哈希表记录每个数出现的次数，然后遍历哈希表统计出现次数大于1的数的个数，即为能够删除的数的个数。

具体实现：

def max_removed_num(a):
    count = {}
    for num in a:
        count[num] = count.get(num, 0) + 1
    removed_num = 0
    for num in count:
        if count[num] > 1:
            removed_num += count[num]
    return removed_num

时间复杂度：

遍历数组需要O(n)的时间，遍历哈希表统计出现次数大于1的数的个数需要O(hash_size)的时间，其中hash_size为哈希表的大小，最坏情况下为O(n)，因此总时间复杂度为O(n)或O(nlogn)。

空间复杂度：

空间复杂度为O(hash_size)，最坏情况下为O(n)。