Python数组操作：高效移除N个最小元素并保留顺序

def remove_smallest_naive(n, arr):
    if n > 0:
        # 错误：smallest_nums 存储的是值，而不是具体的元素实例
        smallest_nums = sorted(arr)[:n] 
        # 错误：这会移除所有与 smallest_nums 中值相同的元素
        return [x for x in arr if x not in smallest_nums]
    return arr

def remove_smallest(n, arr):
    # 1. 处理边缘情况
    if n <= 0:
        return arr
    if not arr or n >= len(arr): # 如果 n 大于等于数组长度，返回空列表
        return []

    # 2. 识别要移除的 n 个元素的值
    # smallest_nums 包含了要移除的 n 个元素的具体值（可能包含重复）
    smallest_nums = sorted(arr)[:n]

    # 3. 确定“边界”值
    # greatest 是 smallest_nums 中最大的那个值，它可能是重复的
    greatest = smallest_nums[-1]

    # 4. 计算边界值的移除数量
    # count 记录了在 smallest_nums 中，有多少个元素的值等于 greatest。
    # smallest_nums.index(greatest) 找到第一个 greatest 的索引。
    # len(smallest_nums) - smallest_nums.index(greatest) 
    # 得到了 smallest_nums 中从第一个 greatest 到末尾的元素数量，
    # 这就是需要移除的 greatest 实例的数量。
    count_to_remove_greatest = len(smallest_nums) - smallest_nums.index(greatest)

    # 5. 构建结果列表
    result = []
    # 辅助集合，用于快速判断一个值是否在 smallest_nums 中且小于 greatest
    # 注意：这里不能直接用 set(smallest_nums) 因为会丢失重复信息
    # 我们需要一个更精确的机制来跟踪哪些值需要被移除

    # 更好的方法是直接遍历原始数组，并使用一个可变的计数器来处理 greatest

    # 将 smallest_nums 转换为一个可变列表，方便移除已处理的元素
    # 或者使用一个 Counter，但这里直接用列表和 index/pop 更直观
    temp_smallest_nums = list(smallest_nums) # 复制一份，避免修改原 sorted 列表

    for x in arr:
        # 检查当前元素 x 是否是我们需要移除的元素之一
        if x in temp_smallest_nums:
            # 如果是，找到它的第一个索引并移除它，表示这个实例已经被“处理”了
            temp_smallest_nums.remove(x)
        else:
            # 如果不在 temp_smallest_nums 中，说明它不是 n 个最小的元素之一
            # 或者它是一个 greatest 值，但我们已经移除了足够多的 greatest
            result.append(x)

    # 上面的逻辑简化了，但没有完全实现题目中“索引靠前的优先移除”的精确性
    # 考虑回最初的“海象运算符”方案，它更精确地处理了 greatest 的移除

    # 重新实现基于海象运算符的精确逻辑
    final_result = []
    # count_to_remove_greatest 此时已经包含了需要移除的 greatest 实例数量

    for x in arr:
        # 如果 x 不在 smallest_nums 中 (即 x 比 smallest_nums 中的所有值都大)
        # 或者 x 是 greatest 但我们已经移除了足够的 greatest (count_to_remove_greatest 变为负数)
        # 那么就保留 x
        if x not in smallest_nums or \
           (x == greatest and (count_to_remove_greatest := count_to_remove_greatest - 1) < 0):
            final_result.append(x)

    # 需要注意的是，`x not in smallest_nums` 这一部分在有重复值时仍有问题
    # 例如 smallest_nums = [1, 1], arr = [1, 1, 2]. 
    # 如果 x = 1, x in smallest_nums 为 True.
    # 如果 x = 1, 且 x == greatest (greatest = 1), 
    # 那么 (count_to_remove_greatest := count_to_remove_greatest - 1) < 0 会决定是否保留。
    # 
    # 这里的 `x not in smallest_nums` 应该理解为 `x` 不属于 `smallest_nums` 中那些需要被移除的特定实例
    # 
    # 更准确的实现是：维护一个要移除的元素值的计数器

    # 使用 Counter 来追踪要移除的每个值的数量
    from collections import Counter

    # 统计 smallest_nums 中每个值出现的次数
    remove_counts = Counter(smallest_nums)

    final_result_v2 = []
    for x in arr:
        if remove_counts[x] > 0:
            # 如果当前元素 x 是要移除的元素之一，且还有剩余的移除额度
            remove_counts[x] -= 1 # 消耗一个移除额度
        else:
            # 否则，保留该元素
            final_result_v2.append(x)

    return final_result_v2

from collections import Counter

def remove_smallest(n, arr):
    # 1. 处理边缘情况
    if n <= 0:
        return arr
    if not arr or n >= len(arr):
        return []

    # 2. 识别要移除的 n 个元素的值
    # 对数组进行排序以找到 n 个最小的元素
    # 注意：这里我们只关心值，不关心原始索引
    smallest_elements_to_remove = sorted(arr)[:n]

    # 3. 使用 Counter 统计每个值需要移除的次数
    # 例如，如果 smallest_elements_to_remove 是 [1, 1, 2]，
    # 那么 remove_counts 将是 {1: 2, 2: 1}
    remove_counts = Counter(smallest_elements_to_remove)

    # 4. 遍历原始数组，构建结果列表
    result = []
    for x in arr:
        # 如果当前元素 x 在 remove_counts 中有对应的移除次数
        # 并且该次数大于 0 (表示这个值的实例还需要被移除)
        if remove_counts[x] > 0:
            remove_counts[x] -= 1  # 减少一次移除计数
        else:
            # 否则，保留该元素
            result.append(x)

    return result

print(remove_smallest(1, [1, 1]))         # 预期: [1]
print(remove_smallest(0, [1, 2, 3]))      # 预期: [1, 2, 3]
print(remove_smallest(3, [1, 2, 3]))      # 预期: []
print(remove_smallest(1, [5, 3, 2, 1, 4])) # 预期: [5, 3, 2, 4] (移除 1)
print(remove_smallest(2, [5, 3, 2, 1, 4])) # 预期: [5, 3, 4] (移除 1, 2)
print(remove_smallest(2, [1, 2, 1, 2, 3])) # 预期: [1, 2, 3] (移除第一个 1 和第一个 2)
print(remove_smallest(3, [10, 1, 10, 1, 10])) # 预期: [10, 10] (移除两个 1 和一个 10)
print(remove_smallest(5, [1, 1, 1, 1, 1])) # 预期: []
print(remove_smallest(2, []))             # 预期: []