在两个排序的list中找全部相同元素

面试题
给两个排序的list，A和B，找出A和B中全部的相同元素。
len(A) = n
len(B) = m
m >> n
Integer.MIN_VALUE <= A[i] <= Integer.MAX_VALUE
Integer.MIN_VALUE <= B[i] <= Integer.MAX_VALUE


eg
[1,2,3,4,5] [1,3,5,8] return [1,3,5]


我觉得是没有log复杂度的解法，最好只能是m+n，如果m>>n 可能nlogm会更优，别的都是细节上调一调了，复杂度是不可能更好的。
面的时候一直想说不可能比线性复杂度更好，我看他一直叫我优化我也不知道该不该说不可能，估计面试挂了。
面的时候我一直在想二分缩小范围来想办法让它log复杂度，事后仔细想想，就算写出来了也是线性复杂度的。
唉，就这样吧，没想到终面是这样的。


不知道有没有别的log的解法或者更快解法。



补充内容 (2024-10-16 13:37 +08:00):

分享我的code，当然面试的时候出了错，不过这个并不是log复杂度，最坏情况一样很垃。


if __name__ == '__main__':
    A = [1, 2, 3, 4, 4, 8]
    B = [0, 1, 2, 3, 4, 4, 4, 5, 6, 7, 10]
    import bisect
    n = 0
    m = 0
    ans = []
    while n < len(A) and m < len(B):
        m = bisect.bisect_left(B, A[n], m)
        n = bisect.bisect_left(A, B[m], n)
        if n < len(A) and m < len(B) and A[n] == B[m]:
            ans.append(A[n])
        m+=1
        n+=1
    print(ans)

这问题确实很搞笑，因为正常的解决思路就是俩set或者俩map互相比较。如果非得钻二分查找，那又要掰扯n必须是 log n*m的长度才是最优解，如果那句话说错或者面试官根本想的不是这个，那就踩马蹄子上啦。真是无语。挂了也没办法，这种题纯粹猜闷。

我感觉time complexisty 是 Nlog(logM), 因为我们还是要遍历数组n，只是每次的M长度减半。
（不过gpt 说是 O(logM⋅logN)，考虑到这不是第一次它胡说八道了，也就不继续调查了。FYI）
另外可能有bug，懒得调了。

1. def getSameElement(m, n):
   
2.     ans = []
   
3. 
   
4.     def helper(lst1, start1, end1, lst2, start2, end2):
   
5.         if start1 > end1: return
   
6. 
   
7.         # binary search
   
8.         m1 = start1 + (end1 - start1) // 2
   
9.         m2 = binarySearch(lst2, start2, end2, lst1[m1])
   
10.         if lst1[m1] == lst2[m2]:
    
11.             ans.append(lst1[m1])
    
12.             helper(lst1, start1, m1-1, lst2, start2, m2-1)
    
13.             helper(lst1, m1+1, end1, lst2, m2+1, end2)
    
14.         else:
    
15.             helper(lst1, start1, m1-1, lst2, start2, m2)    # not m2-1
    
16.             helper(lst1, m1+1, end1, lst2, m2+1, end2)
    
17. 
    
18. 
    
19.     def binarySearch(lst, start, end, target):
    
20.         l, r = start, end
    
21.         while l <= r:
    
22.             m = l + (r-l) // 2
    
23.             if lst[m] < target: l = m + 1
    
24.             elif lst[m] > target: r = m - 1
    
25.             else: return m
    
26. 
    
27.         return r
    
28. 
    
29. 
    
30.     # left half, left half, right half, right half
    
31.     helper(m, 0, len(m)-1, n, 0, len(n)-1)
    
32.     return ans
    
33. 
    
34. print(getSameElement([1,2,3,4,5],[1,3,5,8]))

复制代码

给个code吧，面试的时候没写出来 ，平常用Java刷题的想用bisect省事，结果忘记了lo=?
时间复杂度 O(m+n)
空间复杂度 O(1)

if __name__ == '__main__':
    A = [1, 2, 3, 4, 4, 8]
    B = [0, 1, 2, 3, 4, 4, 4, 5, 6, 7, 10]
    import bisect

    n = 0
    m = 0
    ans = []
    while n < len(A) and m < len(B):
        m = bisect.bisect_left(B, A[n], m)
        n = bisect.bisect_left(A, B[m], n)

        if n < len(A) and m < len(B) and A[n] == B[m]:
            ans.append(A[n])
        m+=1
        n+=1


    print(ans)

List 有没有duplicate?

zys87126 发表于 2024-10-15 22:48
List 有没有duplicate?

可有可无，没有指定

把b的元素在sorted的a里bs，如果无重复元素的话.

sun090807 发表于 2024-10-15 23:02
把b的元素在sorted的a里bs，如果无重复元素的话.

这样是mlogn，比nlogm还差
并不是log解法啊

knkm 发表于 2024-10-15 20:07:47
这样是mlogn，比nlogm还差
并不是log解法啊

说反了，ab换一下，m>>n时候 mlgn <<m+n

在b的里面二分找a的元素吧。。。
nlogm的时间这样。。

未必是让你优化时间， 这题空间可以优化到o(1)。 而且最好的做法，时间复杂度在 n 和 m
+ n之间， 如果你的解放是单纯的m + n 确实可以优化。

而且一般情况下，要主动比较nlogm 和m+ n的大小， 说明什么情况mlogn更小，什么情况 m + n 更小

rymwer 发表于 2024-10-16 00:29
未必是让你优化时间， 这题空间可以优化到o(1)。 而且最好的做法，时间复杂度在 n 和 m
+ n之间， 如果你 ...

三种办法
最垃圾的HashMap 时间O(m+n) 空间O(n)
双指针 时间O(m+n) 空间O(1)
二分查找 时间O(nlogm) 空间 O(1)

应该不会有别的方法了，就算有也是根据以上方法进行稍微调整。
我和面试官说的通过两次二分查找缩小查找范围，时间复杂度也是就是先在B查A[0]然后查到后在A差B[i]但是仔细想想时间复杂度也是一样的，没啥变化 （就是改进双指针）。