Monday, November 23, 2009

数组过滤之bitmap解法

求一个数组中过滤掉重复的元素,并保证原有的元素均存在。

>>> data
['a', 'a', 'z', 'b', 'a', 'b', 'c']
>>> def foo(f,n=0):
    if f%2 != 0:
        l.append(n)
    if f/2 == 1:
        l.append(n+1)
        return l
    n += 1
    foo(f/2,n)

   
>>> l = []
>>> p = foo(reduce(lambda x,y:x|y,map(lambda x:1<<(128-ord(x)),data)))
>>> r = map(lambda x:chr(128-x),l)
>>> r
['z', 'c', 'b', 'a']

March Liu大法

>>def refoo(d, k):
c = d.get(k, 0)
d[k] = c+1
return d

>>> map(lambda p: p[0], filter(lambda p:p[1]==1, reduce(refoo, data, {}).iteritems()))

2 comments:

  1. nnd,装逼写了一个算法

    ReplyDelete
  2. lee的变态方法:
    >>> a
    [8, 1, 2, 3, 2, 5, 8]
    >>> list(set(a) - set(reduce(lambda xs, x:xs.remove(x) and 1 or xs, list(set(a)), copy.copy(a))))
    [1, 3, 5]

    ReplyDelete