# Untitled

By: a guest on Jun 9th, 2012  |  syntax: Python  |  size: 1.75 KB  |  hits: 26  |  expires: Never
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. """
2. Data una lista l di interi, si vuole modificarla cancellando tutti gli elementi i cui valori compaiono esattamente una volta, mantenendo lo stesso ordine che gli elementi avevano inizialmente. (p.e. se l'ingresso e' l = [6, 1, 6, 1, 4, 1, 1, 3, 5] allora il risultato e' L = [6, 1, 6, 1, 1, 1]). Si scriva una procedura utilizzando gli operatori per le liste visti lezione.
3. """
4.
5. # returns the number of occurrences of element e in list l
6. def get_occurrences (l, e):
7.         count = 0
8.         for x in l:
9.                 if x == e: count += 1
10.         return count
11.
12. # remove elements according to exam question
13. # complexity: O(n^2)
14. def fun1 (l):
15.         lc = list(l) # copy of the input list (is this really needed? we can re-use the same list for occurrences count)
16.         i = 0 # pointer to the first element of the list l
17.         while i < len(l):
18.                 occurrences = get_occurrences(lc, l[i]) # get number of occurrences of current element
19.                 if occurrences == 1: del(l[i]) # if it appears only one time in the list delete it
20.                 else: i += 1 # consider the next element otherwise
21.
22.         return l
23.
24. # remove elements according to exam question
25. # complexity: O(n)
26. def fun2 (l):
27.         d = dict() # create an empty dictionary (hash table)
28.
29.         # for each element in input list
30.         for e in l:
31.                 if d.has_key(e): d[e] += 1 # if this element has been already added to the dictonary increment the related number
32.                 else: d[e] = 1 # set up the related number of this element to 1 (occurrence) otherwise
33.
34.         # return the list in which all elements that appears only one time have been deleted
35.         return [ e for e in l if d[e] > 1 ]
36.
37. # like fun1 but much more simple!
38. # complexity: O(n^2)
39. def fun3 (l):
40.         return [ e for e in l if l.count(e) > 1 ]
41.
42. # main
43. l = [6, 1, 6, 1, 4, 1, 1, 3, 5]
44. print fun1(l)
45. print fun2(l)
46. print fun3(l)