CODEWITHSUNDEEP
pythonqueue
Deepbread
Deepbread

Reputation: 7

Count distinct values in a queue

I am trying to implement the method that counts the number of distinct values in a queue. For example, if the queue looks like this: [1, 2, 2, 4, 4, 4, 8, 8, 10], then the method should return 5.

So I create the function like this:

def count_distinct(self) -> int:

        # Test case
        Q = [0, 1, 1, 2, 3, 4, 5, 5, 7, 7, 9, 9, 9, 11, 11]

        if Q.is_empty():
            return 0
        
        count = 1
        current = Q.dequeue()
        
        while (Q.is_empty() is False):

            next = Q.dequeue()

            if current != next:
                count += 1
            
            current = next

        return count

But, the result was weird.

Expected result: 9

My result: 15

Does anyone know what the problem is? Thanks

Upvotes: 0

Views: 825

Answers (4)

Rarblack
Rarblack

Reputation: 4664

You can simply just first sort and then count the number unless it is not the same as the previous one.

a = [1, 2, 2, 4, 4, 4, 8, 8, 10]
a = sorted(a)

last = a[0]
count = 1

for i in range(1, len(a)):
    if a[i] == last: 
        continue
    last = a[i]
    count += 1

print(count)

In your case, let's assume that your code is running and you have customly made all these extra methods(dequeue and etc.). In this case, most probably the reason is that your list is getting not sorted as you have created it.

Upvotes: 0

zhenhua32
zhenhua32

Reputation: 264

Is queue like python queue.Queue?

If Queue is ordered, your function look right.

import queue

def count_distinct() -> int:

    # Test case
    Q = queue.Queue()
    for x in [0, 1, 1, 2, 3, 4, 5, 5, 7, 7, 9, 9, 9, 11, 11]:
        Q.put(x)

    if Q.empty():
        return 0
    
    count = 1
    current = Q.get()
    
    while (Q.empty() is False):

        next = Q.get()

        if current != next:
            count += 1
        
        current = next

    return count

It return 9.

Upvotes: 1

ThePyGuy
ThePyGuy

Reputation: 18406

Just out of curiosity

Why don't you use set and get the length? Set only holds the unique values, and you don't seem to be concerned about any particular order these values appear.

>>> len(set(Q))
9

Upvotes: 1

Corralien
Corralien

Reputation: 120391

Use Counter from itertools:

from collections import Counter

l = [1, 2, 2, 4, 4, 4, 8, 8, 10]
c = Counter(l)

>>> len(c)
5

For your test case:

>>> len(Counter(Q))
9

Upvotes: 0

Related Questions