时间戳

首页 > 解决方案 > Function which eliminates specific elements from a list in an efficient way

python - Function which eliminates specific elements from a list in an efficient way

问题描述

I want to create a function (without using libraries) which takes as input three integer numbers (>0) (a,b,c) , for example:

a = 6
b = 6
c = 3

and returns a list containing c elements (so in this case the returned list should contain 3 elements) taken from a list of a numbers (so in this case the initial list is [1,2,3,4,5,6]). The c elements of the returned list have to be the ones that managed to remain in the initial list after removing a number every b positions from the list of a elements until len(return_list) = c.

So for a = 6, b = 6 and c = 3 the function should do something like this:

1) initial_list = [1,2,3,4,5,6] 
2) first_change = [2,3,4,5,6] #the number after the 6th (**b**) is 1 because after the last element you keep counting returning to the first one, so 1 is canceled
3) second_change = [2,4,5,6] #you don't start to count positions from the start but from the first number after the eliminated one, so new number after the 6th is 3 and so 3 is canceled
4) third_change = [2,4,5] #now the number of elements in the list is equal to **c**

Notice that if, when counting, you end up finishing the elements from the list, you keep the counting and return to the first element of the list.

I made this function:

def findNumbers(a,b,c):  
count = 0
dictionary = {}
countdown = a
for x in range(1,a+1):
    dictionary[x] = True
while countdown > c:
    for key,value in dictionary.items():
        if value == True:
            count += 1
            if count == b+1:
                dictionary[key] = False
                count = 0
                countdown -= 1
return [key for key in dictionary.keys() if dictionary[key] == True]

It works in some cases, like the above example. But it doesn't work everytime. For example:

findNumbers(1000,1,5)

returns:

[209, 465, 721, 977]    #wrong result

instead of:

[209, 465, 721, 849, 977] #right result

and for bigger numbers, like:

findNumbers(100000, 200000, 5)

it takes too much time to even do its job, I don't know if the problem is the inefficiency of my algorithm or because there's something in the code that gives problems to Python. I would like to know a different approach to this situation which could be both more efficient and able to work in every situation. Can anyone give me some hints/ideas? Thank you in advance for your time. And let me know if you need more explanations and/or examples.

标签： pythonpython-3.xloops

解决方案

您可以跟踪删除的最后一个列表项的索引，如下所示：

def findNumbers(a, b, c):
    l = list(range(1, a + 1))
    i = 0
    for n in range(a - c):
        i = (i + b) % (a - n)
        l.pop(i)
    return l

这样findNumbers(6, 6, 3)返回：

[2, 4, 5]

并findNumbers(1000, 1, 5)返回：

[209, 465, 721, 849, 977]

并findNumbers(100000, 200000, 5)返回：

[10153, 38628, 65057, 66893, 89103]

推荐阅读