CODEWITHSUNDEEP
pythonarrayslistloopsunique
freezefry
freezefry

Reputation: 158

Counting number of list entries that occur 1 time

I'm trying to write a Python function that counts the number of entries in a list that occur exactly once.

For example, given the list [17], this function would return 1. Or given [3,3,-22,1,-22,1,3,0], it would return 1.

** Restriction: I cannot import anything into my program.

The incorrect code that I've written so far: I'm going the double-loop route, but the index math is getting over-complicated.

def count_unique(x):
  if len(x) == 1:
    return 1
  i = 0
  j = 1
  for i in range(len(x)):
    for j in range(j,len(x)):
      if x[i] == x[j]:
        del x[j]
        j+1
    j = 0
  return len(x)

Upvotes: 0

Views: 1200

Answers (5)

MK.
MK.

Reputation: 34537

lst =  [3,3,-22,1,-22,1,3,0]
len(filter(lambda z : z[0] == 1, 
           map(lambda x : (len(filter(lambda y : y == x, lst)), x), lst)))

sorry :)

Your solution doesn't work because you are doing something weird. Deleting things from a list while iterating through it, j+1 makes no sense etc. Try adding elements that are found to be unique to a new list and then counting the number of things in it. Then figure out what my solution does.

Here is the O(n) solution btw:

lst =  [3,3,-22,1,-22,1,3,0,37]
cnts = {}
for n in lst:
   if n in cnts:
      cnts[n] = cnts[n] + 1
   else:
      cnts[n] = 1

count = 0
for k, v in cnts.iteritems():
   if v == 1:
      count += 1
print count

Upvotes: 3

John Ruddell
John Ruddell

Reputation: 25842

you are making this overly complicated. try using a dictionary where the key is the element in your list. that way if it exists it will be unique

to add to this. it is probably the best method when looking at complexity. an in lookup on a dictionary is considered O(1), the for loop is O(n) so total your time complexity is O(n) which is desirable... using count() on a list element does a search on the whole list for every element which is basically O(n^2)... thats bad

from collections import defaultdict
count_hash_table = defaultdict(int) # i am making a regular dictionary but its data type is an integer
elements = [3,3,-22,1,-22,1,3,0]
for element in elements:
    count_hash_table[element] += 1 # here i am using that default datatype to count + 1 for each type

print sum(c for c in count_hash_table.values() if c == 1):

Upvotes: 2

colidyre
colidyre

Reputation: 4666

A more simple and understandable solution:

l =  [3, 3, -22, 1, -22, 1, 3, 0]
counter = 0

for el in l:
    if l.count(el) == 1:
        counter += 1

It's pretty simple. You iterate over the items of the list. Then you look if the element is exactly one time in the list and then you add +1. You can improve the code (make liste comprehensions, use lambda expressions and so on), but this is the idea behind it all and the most understandable, imo.

Upvotes: 2

LetzerWille
LetzerWille

Reputation: 5658

There is method on lists called count.... from this you can go further i guess. 
for example:

for el in l:
    if l.count(el) > 1:
        continue
    else:
        print("found {0}".format(el))

Upvotes: 1

ShadowRanger
ShadowRanger

Reputation: 155363

Since you can't use collections.Counter or sorted/itertools.groupby apparently (one of which would usually be my go to solution, depending on whether the inputs are hashable or sortable), just simulate roughly the same behavior as a Counter, counting all elements and then counting the number of elements that appeared only once at the end:

def count_unique(x):
    if len(x) <= 1:
        return len(x)
    counts = {}
    for val in x:
        counts[val] = counts.get(val, 0) + 1
    return sum(1 for count in counts.values() if count == 1)

Upvotes: 3

Related Questions