python - Is there a way to remove numbers in a list dependant on conditions of previous number?

Question

I am looking to remove numbers from mylist and need to code something that will do this:

1. Take a look at the first element and remove all other elements in the list that are a increment above and a increment below
2. Your list is now smaller, look at the 2nd element in the list and remove all other elements that again are a increment above and a increment below.
3. Carry on until the end of the list, until you are left with survivors of the purge!

EXAMPLES:

mylist = [1,8,9,3,5,6,2,4]

increment=1

Desired Output:

[1,8,9,3,5,6,4] #number in list observed - 1, removes these numbers in the list: 0 & 2

[1,8,3,5,6,4]   #number in list observed - 8, removes these numbers in the list: 7 & 9

[1,8,3,5,6]     #number in list observed - 3, removes these numbers in the list: 2 & 4

[1,8,3,5]       #number in list observed - 5, removes these numbers in the 

list: 4 & 6

mylist = [1,8,9,3,5,6,2,4]

increment=2

Desired Output:

[1,8,9,5,6,4]  #number in list observed - 1, removes these numbers in the list: -1,0,2,3  

[1,8,5,4]      #number in list observed - 8, removes these numbers in the list: 6,7,9,10  

[1,8,5]        #number in list observed - 5, removes these numbers in the 

list: 3,4,6,7

This has been difficult for me to figure out because the numbers in the list that need to be removed are very far from the number observed. I am working with lists of 675,000 numbers long and need to shred off numbers that I don't need, within an increment of 1098.

Answer 1

First step is to find out exactly what needs to be removed, in a linear scan:

li = [1,8,9,3,5,6,2,4]
increment = 1

to_remove = set()
for x in li:
    if x not in to_remove:
        # Number is not going to be removed by previous numbers,
        # so it's going to be the next purge candidate.
        for i in range(1, 1 + increment):
            to_remove.add(x - i)
            to_remove.add(x + i)

And then to simply purge:

purged_li = [x for x in li if x not in to_remove]

This has worst case complexity O(nk log(nk)) where n == len(li) and k == increment. You can do better but it going to involve much more complex range query data structures.