1

I have figured out the code that takes a list and returns a list where each element only occurs once. But I cannot figure out what I need to do to have to do to eliminate the numbers with no negative counter part:

such as if a list has the numbers [1,-1,2,-2,3]. It will remove the 3 when the list is returned.

So far I have

def one(a):
  conversion = set()
  conversion_add = conversion.add
  elim = [x for x in a if x not in conversion and not conversion_add(x)]

what do I need to do next? If statements, and what syntax do I need to use to compare positive to negative so I can remove the extra number without a negative?

Much thanks

Blckknght
  • 100,903
  • 11
  • 120
  • 169

2 Answers2

4

Sounds about right:

src = set([1,-1,2,-2,3])
no_match = set(a for a in src if -a not in src)
match = set(a for a in src if -a in src)

Results:

>>> src = set([1,-1,2,-2,3])
>>> no_match = set(a for a in src if -a not in src)
>>> match = set(a for a in src if -a in src)
>>> no_match
set([3])
>>> match
set([1, 2, -1, -2])
hughdbrown
  • 47,733
  • 20
  • 85
  • 108
  • 1
    I have an idea, but may not be suitable for implementation in Python: add a zero into the list, then sort it. Find the zero, then initialize two index-pointers with the index of zero. Move the pointers left and right by one entry each time, and eliminate the smaller unmatch. If this works, it would time O(nlogn) time. – Patrick the Cat Oct 12 '13 at 22:14
  • To get `match` you could do `match = src.difference(no_match)`. This would save a small amount of time, and might be clearer since by definition combination of `match` and `no_match` must equal `src`, and `no_match` and `match` are mutually exclusive. – SethMMorton Oct 12 '13 at 22:24
  • @Mai, I think you mean something like this: http://stackoverflow.com/questions/1283231/given-an-array-of-numbers-find-out-if-3-of-them-add-up-to-0/1284514#1284514 You don't need to add zero. Just start at both ends and terminate when your left and right indexes cross over. – hughdbrown Oct 12 '13 at 22:33
  • @Mai - the `set` version should be O(n), because a Python `set` is based on a hashtable and has amortized O(1) inserts. Therefore, in the asymptotic sense, anything that needs you to sort the items will be slower than this answer unless you can sort in O(n) time. If your data is definitely integers in some bounded range, you *can* sort them in O(n) time, but Python `sort` won't do it - you'd need a radix sort, and still you'd only get performance asymptotically equal to the hashtable/set approach. Nice idea, though. –  Oct 13 '13 at 00:14
  • @Mai - actually, possible proviso - for large integers, computing the hash is presumably O(log m) where m is the integer. A lot of O(n) algorithms turn out to depend on having values in a bounded range or else you actually have O(n log m) - that's the case with filling a hashtable. It's also the case for radix sorting - if you don't bound the integers, performance will be O(n log m) with n the number of integers and m the size of the integers. Reason - an integer value `m` has `log m` digits. –  Oct 13 '13 at 00:56
1

You can do that using filter, and then convert the resulting list to a set:

> x = [1, 2, 3, -2, -4, -1, 4]
> print filter(lambda elem: -elem in x, x)
[1, 2, -2, -4, -1, 4]
Salem
  • 12,808
  • 4
  • 34
  • 54
  • 2
    This is much slower than adding everything to a set and then checking membership against the set. – roippi Oct 12 '13 at 22:05
  • But still perfectly OK if you don't need to care about performance on large lists. For very small lists, it might even be faster. –  Oct 13 '13 at 00:05