在不使用散列的情况下计算列表中不同项目的数量 table

Question

假设我有一个列表（不一定排序）：

lst = [1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 10]

我需要一个 returns 计算列表中唯一元素的函数，在本例中为 10。

我不允许使用 dict 或 set。

我考虑过做类似的事情：

num = len(lst)
for e in lst:
    for i in lst:
        if e == i:
           num -= 1

但显然，它不起作用。谢谢！

Answer 1

试试这个：

任何在列表上执行双重嵌套循环的解决方案在 O(n^2) 时间内运行，以下在 O(n log(n)) 时间内运行。虽然可能有一种方法可以在不使用散列 table 的情况下使用 O(n) 时间解决方案，但我没有看到它。

def count_number_unique(my_list):
    prev = None
    unique_count = 0
    for ele in sorted(my_list):
        if ele != prev:
            unique_count += 1
        prev = ele
    return unique_count

结果：

In [20]: lst = [1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 10]

In [21]: count_number_unique(lst)
Out[21]: 10

In [22]: count_number_unique([1,2,1,9,1,2])
Out[22]: 3

在不使用散列的情况下计算列表中不同项目的数量 table

Count number of distinct items in a list without using a hash table

python

list

distinct