Python教程：高效移除数组中N个最小元素（含重复值处理）

本教程详细探讨了如何在Python中从一个整数数组中移除指定数量`n`的最小元素。文章分析了处理重复值和保持剩余元素顺序的常见陷阱，并提供了一种基于列表推导和计数机制的优化解决方案，确保在面对复杂测试用例时代码的健壮性和准确性。

1. 问题描述

给定一个整数数组 arr 和一个整数 n，任务是从 arr 中移除 n 个最小的元素。在实现过程中，需要严格遵守以下规则：

• 边缘情况处理：
  • 如果 n 大于数组的长度，应返回一个空列表。
  • 如果 n 小于或等于零，应返回原始数组。
• 元素顺序保持：剩余元素的相对顺序必须保持不变。
• 重复值处理：如果数组中存在多个相同值的元素，且这些值属于需要移除的 n 个最小元素范畴，应优先移除那些索引较低（即在原始数组中出现较早）的元素。

2. 常见误区与初始尝试分析

许多初学者在处理此类问题时，可能会尝试一种直观的方法：首先找出 n 个最小的元素值，然后遍历原始数组，将那些不在这些最小元素值列表中的元素保留下来。

以下是这种常见尝试的示例代码：

立即学习“Python免费学习笔记（深入）”；

def remove_smallest_naive(n, arr):
    if n <= 0:
        return arr
    if not arr or n >= len(arr): # Added check for empty array and n >= len(arr)
        return []

    # 找出 n 个最小的元素值
    smallest_nums_values = sorted(arr)[:n]

    # 尝试过滤：如果元素值不在 smallest_nums_values 中，则保留
    return [x for x in arr if x not in smallest_nums_values]

代码分析与缺陷：

尽管此代码在某些简单测试用例中可能通过，但在处理包含重复值的数组时会遇到问题。考虑以下测试用例：

print(remove_smallest_naive(1, [1, 1]))
# 预期输出: [1]
# 实际输出: []

为什么会这样？

1. n = 1, arr = [1, 1]。
2. smallest_nums_values = sorted([1, 1])[:1] 结果为 [1]。这表示我们要移除一个值为 1 的元素。
3. 列表推导 [x for x in arr if x not in smallest_nums_values] 会检查 arr 中的每个 x。
   • 当 x 是 arr[0] (值为 1) 时，1 not in [1] 为 False，所以第一个 1 不会被加入结果列表。
   • 当 x 是 arr[1] (值为 1) 时，1 not in [1] 仍然为 False，所以第二个 1 也不会被加入结果列表。
4. 最终，代码返回一个空列表 []，而不是预期的 [1]。

根本原因： x not in smallest_nums_values 这种过滤方式，会移除 所有 值为 1 的元素，而不仅仅是 n 个特定实例。它没有区分需要移除的 n 个最小元素是 哪些特定位置 的元素，或者说，它没有考虑到 smallest_nums_values 中可能包含多个相同的值，而我们只希望移除其中一部分。

Upscale

AI图片放大工具

85

查看详情

3. 优化方案：精确控制移除数量与实例

要解决上述问题，我们需要一种机制来精确地“消耗”掉 n 个最小元素。这意味着，当一个元素 x 在 arr 中出现时，如果它属于我们希望移除的 n 个最小元素之一，我们只移除 一个实例，而不是所有相同值的实例。

以下是基于原始问题答案提供的优化解决方案，它巧妙地利用了Python的列表推导和赋值表达式（walrus operator :=）来精确控制移除逻辑：

def remove_smallest(n, arr):
    # 1. 处理边缘情况
    if n <= 0 or not arr:
        return list(arr) # 返回副本，避免修改原始列表
    if n >= len(arr):
        return []

    # 2. 找出 n 个最小的元素值
    # smallest_nums 包含 n 个最小元素的值，已排序
    # 例如：arr=[3,1,4,1,5,9,2,6], n=3 => smallest_nums=[1,1,2]
    smallest_nums = sorted(arr)[:n]

    # 3. 识别 n 个最小元素中的最大值及其在 smallest_nums 中的数量
    # greatest: smallest_nums 中最大的值 (例如 2)
    # count: greatest 在 smallest_nums 中出现的次数 (例如 1)
    greatest = smallest_nums[-1]
    count = len(smallest_nums) - smallest_nums.index(greatest)

    # 4. 使用列表推导进行精确过滤
    # 遍历原始数组 arr，根据条件决定是否保留元素 x
    result = []
    for x in arr:
        # 条件一：如果 x 不在 smallest_nums 中，说明它不是 n 个最小元素之一，直接保留。
        # 条件二：如果 x 是 greatest (即 n 个最小元素中的最大值)，并且
        #         我们还没有“移除”所有需要移除的 greatest 实例 (count := count - 1) < 0
        #         当 (count := count - 1) < 0 成立时，表示我们已经移除了足够的 greatest 实例，
        #         当前这个 greatest 应该被保留。
        #         注意：对于小于 greatest 且在 smallest_nums 中的元素，它们会被移除。
        if x not in smallest_nums or (x == greatest and (count := count - 1) < 0):
            result.append(x)
    return result

详细解析：

1. 边缘情况处理：

   • if n
   • if n >= len(arr):：如果 n 大于或等于数组长度，返回空列表。

2. smallest_nums = sorted(arr)[:n]：

   • 这一步获取了 n 个最小元素的 值，并按升序排列。例如，如果 arr = [1, 1, 2, 3] 且 n = 2，smallest_nums 将是 [1, 1]。

3. greatest = smallest_nums[-1] 和 count = len(smallest_nums) - smallest_nums.index(greatest)：

   • greatest 是 smallest_nums 中最大的那个值。在 [1, 1] 的例子中，greatest 是 1。
   • smallest_nums.index(greatest) 找到 greatest 在 smallest_nums 中第一次出现的索引。
   • count 计算 greatest 在 smallest_nums 中出现了多少次。这个 count 代表了我们必须移除的 greatest 值的实例数量。
     • 例如 smallest_nums = [1, 1, 2], greatest = 2. index(2) 是 2. count = 3 - 2 = 1. (需要移除一个 2)
     • 例如 smallest_nums = [1, 1], greatest = 1. index(1) 是 0. count = 2 - 0 = 2. (需要移除两个 1)

4. 列表推导 [x for x in arr if x not in smallest_nums or (x == greatest and (count := count - 1) ：

   • x for x in arr：遍历原始数组 arr 中的每一个元素 x。
   • if x not in smallest_nums：
     • 如果 x 的值不在 smallest_nums 中（即 x 比 n 个最小元素中的最大值还要大），那么它肯定不是要移除的元素，直接保留。
     • 如果 x 的值 在 smallest_nums 中，这个条件为 False，那么会继续评估 or 后面的条件。
   • or (x == greatest and (count := count - 1) ：
     • 这个条件只在 x 的值 在 smallest_nums 中时才有可能成立。
     • x == greatest：如果当前的 x 恰好是 n 个最小元素中的最大值 (greatest)。
     • (count := count - 1) ：这是一个巧妙的计数器。
       • count := count - 1：每当遇到一个等于 greatest 的元素时，count 就会减一。
     • 综合来看 or 逻辑：
       • 对于那些值 严格小于 greatest 且在 smallest_nums 中的元素：x not in smallest_nums 为 False，x == greatest 为 False，所以整个条件为 False，这些元素会被移除。这符合要求。
       • 对于那些值等于 greatest 的元素：
         • 前 count 个遇到的 greatest 元素：x not in smallest_nums

以上就是Python教程：高效移除数组中N个最小元素（含重复值处理）的详细内容，更多请关注php中文网其它相关文章！