在 Python 中的两个列表中使用贪心算法

Question

我们观察到一个由 int 值 n 和两个列表 A 和 B 解释的特定数据样本，其中两个列表包含整数元素或范围从 1 到 n，每个列表中的元素不重复。（但是，两个列表中可能有相同的元素。）

n表示观察样本的大小
A 中的元素表示样本中 'taken out' 的数字。因此，如果 n=5 和 A=[2,3]，我们得到的样本的大小将是 3.
B 中的元素表示 'put back into' 样本中的数字。结果样本的最大大小不能超过 n.
但是，只有当且仅当 A 中的元素等于 B 中的元素时，才能将 B 中的元素放回原处，或者比 B 中的元素小一或大一。例如，如果 n=5, A=[2,3], B=[4]，我们的样本大小将是 4，因为 A 中存在一个元素比 B 中的元素小一个。
最后，B中的元素如果是'put back in'只考虑一次。如果n=5, A=[2,3,5], B=[3,4]，即使B中的元素各满足两次条件，结果样本的大小仍然是4.

部分测试用例给出：

n   A       B           return
5   [2, 4]  [1, 3, 5]   5
5   [2, 4]  [3]         4
3   [3]     [1]         2

我知道这是一种贪心算法（我不是很熟悉），但我也尝试了以下方法：

def solution(n, A, B):
    count = n - len(A)
    for i in range(len(B)):
        if B[i]-1 in A:
            count += 1
        elif B[i]+1 in A:
            count += 1
        elif B[i] in A:
            count += 1
        else:
            count += 0
    if n > count:
        answer = count
    else:
        answer = n
    return answer

虽然这看起来可行，但它没有考虑到 B 中的元素一旦放回原处就无法考虑。我可以对我的代码进行任何编辑吗？这个问题将如何得到最佳解决？

Answer 1

我想关键是使用 set() 以便首先检索没有任何重叠元素的集合，然后开始删除已经过去的元素（这与我的初始代码类似）。

def solution(n, A, B):
  B_uniq = set(B)-set(A)
  A_uniq = set(A)-set(B)
  for i in B_uniq:
    if i-1 in A_uniq:
      A_uniq.remove(i-1)
    elif i+1 in A_uniq:
      A_uniq.remove(i+1)
  return n-len(A_uniq)

在 Python 中的两个列表中使用贪心算法

Using greedy algorithm within two lists in Python

python

list

greedy