根据它们的相互关系过滤掉列表中的元素

Question

我正在处理一个有趣的 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) 会给我一个结果 3micro_world([20, 15, 10, 15, 20, 25], 5) 将给我一个结果 1我正在考虑使用列表理解来过滤掉不符合上述标准的元素，从而获得我想要的元素。但我不确定如何继续，因为它涉及列表中每个元素之间的关系。result = [ i for i in bacteria if ... ]我的 if 语句应该使用什么？如果这不是一个好方法，我该怎么办？谢谢。编辑：这两个答案都为我提供了非常好的指导。但是关于细菌列表中的重复值只有一件小事。例如，如果输入bacteria = [3, 3]即使这只是一个块，结果应该是 2，因为 3 ！> 3 因此两者都不会被删除。

Answer 1

您实际上是在尝试将您的数字列表分组到块中，其中每个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]]

最后我们计算chunk的数量，从而得到想要的结果：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

Answer 2

这是一个使用的解决方案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])]

如果你只对元素的数量感兴趣，而不对元素本身感兴趣，那么你可以修改 ie 第二个版本，如下所示：

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)