我正在研究一个有趣的python问题：
给定整数、细菌和正整数常数 K 的列表，如果有两个元素 i 和 j 满足以下条件：
j < i <= j + K
设计一个函数来使 I 保留并删除 J，并返回列表中尽可能少的元素数。
功能：micro_world(bacteria, K)
例如
bacteria = [101, 53, 42, 102, 101, 55, 54]
K = 1
最终结果应为
[42,102,55]
因此应返回 3。
同样地
micro_world([101, 53, 42, 102, 101, 55, 54], 1)会给我一个 3 的结果
micro_world([20, 15, 10, 15, 20, 25], 5)会给我一个 1 的结果
我正在考虑使用列表理解来过滤掉不符合上述标准的元素，从而获得我想要的元素。但我不确定如何继续它，因为它涉及列表中每个元素之间的关系。
result = [ i for i in bacteria if ... ]
我应该用什么作为我的 if 语句？
如果这不是一个好方法，我该怎么办？
谢谢。
编辑： 这两个答案都为我提供了非常好的指导。但是关于细菌列表中的重复值，只有一件小事。例如，如果输入
bacteria = [3, 3]
即使这只是一个块，结果应该是 2，因为 3 ！> 3 因此两者都不会被删除。
您实际上是在尝试将数字列表分组为块，其中每个数字与该块中的另一个数字相距不到k。因为我不善于解释事情，让我们看一个例子：
bacteria = [101, 53, 42, 102, 101, 55, 54]
K = 1
首先，我们要对该列表进行排序，以便按其大小排列数字：
[102, 101, 101, 55, 54, 53, 42]
现在我们迭代列表，并在每次较大的细菌无法吞下较小的细菌时创建一个新的数字块：
[[102, 101, 101], [55, 54, 53], [42]]
最后，我们计算块的数量，从而获得所需的结果：3。
法典：
def micro_world(bacteria, k):
# sort the list descendingly
bacteria = sorted(bacteria, reverse=True)
# loop over the list but skip all the "swallowed" bacteria
i = 0
result = 0
while i < len(bacteria):
bacterium_size = bacteria[i]
# while the difference between the numbers is <= k, the smaller
# bacterium is swallowed
bigger_bacterium_exists = False
while i+1 < len(bacteria):
difference = bacterium_size - bacteria[i+1]
# if the difference is too big, it can't be swallowed
if difference > k:
break
# if there are two bacteria of the same size, they can't swallow
# each other. But if a bigger bacterium exists, it can swallow
# them both
if difference == 0 and not bigger_bacterium_exists:
break
# all conditions are met, the bacterium is swallowed
bacterium_size = bacteria[i+1]
i += 1
bigger_bacterium_exists = True
# at this point, the bacterium has swallowed everything it can.
# Increment the result counter and move on to the next bacterium.
result += 1
i += 1
return result
这是一个使用numpy的解决方案：
import numpy as np
def micro_world(bacteria, K):
# convert bacteria list to a numpy array:
bacteria = np.asarray(bacteria)
# sort array and remember the indices used for sorting:
sarg = np.argsort(bacteria)
sortedbac = bacteria[sarg]
# compute differences between adjacent elements:
diff = np.ediff1d(sortedbac, K + 1)
# throw away elements that are too close to neighbors
# (find indices of the elements to keep):
idx = np.flatnonzero(diff > K)
# create a new list that meets selection criteria:
return bacteria[np.sort(sarg[idx])]
这是一个"纯"的Python实现：
def micro_world(bacteria, K):
# sort array and remember the indices used for sorting:
sarg = [i[0] for i in sorted(enumerate(bacteria), key=lambda x: x[1])]
sortedbac = [bacteria[i] for i in sarg]
# compute differences between adjacent elements:
diff = [j - i for i, j in zip(sortedbac[:-1], sortedbac[1:])] + [K + 1]
# throw away elements that are too close to neighbors
# (find indices of the elements to keep):
idx = [i for i, v in enumerate(diff) if v > K]
# create a new list that meets selection criteria:
return [bacteria[i] for i in sorted([sarg[i] for i in idx])]
如果您只对元素的数量感兴趣，而不是元素本身，那么您可以修改第二个版本，如下所示：
def micro_world(bacteria, K):
sortedbac = sorted(bacteria)
diff = [j - i for i, j in zip(sortedbac[:-1], sortedbac[1:])] + [K + 1]
return sum(1 for v in diff if v > K)
然后，numpy版本将变为：
def micro_world(bacteria, K):
return np.sum(np.ediff1d(np.sort(bacteria), K + 1) > K)