如何解决此二分搜索代码中 int 的问题

Question

a = [1,2,2,1]
b = [2,2]

if len(a) > len(b):
    my_list = a
    target = b
else:
    my_list = b
    target = a
ans = []
min = 0
max = len(my_list) -1

for i in target: #2
    while min <= max: #min = 0 max = 3
        mid = (min+max)//2 #1
        guess = my_list[mid] # index-1(2 -value)
        if guess == i: #2==2
            ans.append(guess)
            my_list = my_list.pop(my_list[mid])
        if guess < i:
            min = mid+1
        else:
            max = mid-1

我正在努力解决问题： 给定两个整数数组 a 和 b，返回它们交集的数组。结果中的每个元素必须是唯一的，您可以按任何顺序返回结果。

示例1：

输入：nums1 = [1,2,2,1]，nums2 = [2,2]

输出：[2]

但是出现错误：

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[95], line 14
     12 while min <= max: #min = 0 max = 3
     13     mid = (min+max)//2 #1
---> 14     guess = my_list[mid] # index-1(2 -value)
     15     if guess == i: #2==2
     16         ans.append(guess)

TypeError: 'int' object is not subscriptable
    enter code here

为什么会发生这种情况以及如何解决？ P.S: 请不要关注其他可能的错误，我想自己处理

Answer 1

修复错误

问题在于 .pop() 函数无法按照您在程序中使用它的方式工作，就像 slothrop 指出的那样。要删除列表中索引 i 处的项目，您只需执行

myList.pop(i)

即可。所以这是你的代码中遇到的第一个问题。

修复逻辑

这应该可以解决您的错误，但是您的代码仍然无法完成您提到的任务。首先，您需要确保您正在排序列表中执行二分搜索，其中

a

不是 [1, 2, 2, 1]。因此，您需要预先使用 built-in sort 函数对其进行排序。其次，即使删除了在数组中找到的值，它也只会删除它的一个实例，因此最终可能会出现重复项。因此，最好使用 set 来存储结果而不是列表，因为集合不允许重复。最后，代码中最重要的错误是，每次结束二分搜索时，您都没有重置最大值和最小值。您保留之前的最大值和最小值，这意味着交集将无法正确执行。

a = [1, 2, 2, 1]
b = [2, 2]

if len(a) > len(b):
    my_list = a
    target = b
else:
    my_list = b
    target = a
ans = set()
min = 0
max = len(my_list)-1
my_list.sort() # sort for binary search
for i in target:
    min = 0 # reset min
    max = len(my_list)-1 # reset max
    while min <= max:
        mid = (min+max)//2
        guess = my_list[mid]
        if guess == i:
            ans.add(guess)
            my_list.pop(mid)
            break # break loop
        elif guess < i:
            min = mid+1
        else:
            max = mid-1
print(list(ans)) # turn into list

替代解决方案

但是，大部分代码都是不需要的，因为您可以非常轻松地将两个列表转换为集合，然后使用 python 的

intersection_update()

函数将它们连接在一起。