Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
4.4k views
in Technique[技术] by (71.8m points)

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

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

1.4m articles

1.4m replys

5 comments

57.0k users

...