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

Question

Say I have a list (not necessarily sorted):

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

I need a function that returns count of unique elements in a list, in this case 10.

I am not allowed to use dict or set.

I thought about doing something like:

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

But clearly, it does not work. Thanks!

I am expecting 10 but I cannot use set. It has to use == and nothing else. That's the catch. — Charlie Baker, Mar 29 '15 at 03:33
So you need to count number of unique values and you know that the list is sorted? — Akavall, Mar 29 '15 at 03:45
Sure, I guess... But I'm not allowed to use "set" though; this is just an example. I'm actually handling class instances, and I keep encountering errors that they are unhashable if I use a set. — Charlie Baker, Mar 29 '15 at 03:54
I voted to reopen because `OP` cannot use `set`, and all the top voted answers use `set`. I believe this is a different question, and answers to that question do not answer this question. — Akavall, Mar 29 '15 at 04:06
@Martijn Pieters, I believe the title of this question is misleading, but if it is changed to, say: `Count number of distinct items in a list without using a hash table.`, it will have make it clear that this question is different from the one you marked it as duplicate of. — Akavall, Mar 29 '15 at 14:39
@Akavall the requirements exclude using a dictionary, not a set. Using `len()` on the result of `set()` is a very small step to make from the duplicate. — Martijn Pieters, Mar 29 '15 at 14:47
@MartijnPieters, The OP is not allowed to use `set` either, in the comments the OP says" `But I'm not allowed to use "set".` — Akavall, Mar 29 '15 at 14:54
@Akavall then by all means improve the question. Edit it, clean it up, incorporate those details in the post. Editing will put it in the reopen queue, a good edit can easily lead to a reopen that way. — Martijn Pieters, Mar 29 '15 at 14:56

Akavall · Accepted Answer · 2015-03-29T03:58:14.613

Try this:

Any solution that does a double nested loop over a list runs in O(n^2) time, the following runs in O(n log(n)) time. Though there might be a way to come with O(n) time solution without using a hash table, I don't see it.

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

Result:

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

`This function should return: 10 ` – Avinash Raj Mar 29 '15 at 03:29 — Avinash Raj, Mar 29 '15 at 03:29

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

1 Answers1