用函数式编程求两个排序数组的相同元素计数

Question

示例： 给定nums1=[1，2，3，4]，nums2=[2，3]，返回2

我有命令式的解决方案，使用python，算法复杂度为O（m+n）：

def sameElementsCount(nums1, nums2):
    count = 0
    len1 = len(nums1)
    len2 = len(nums2)
    i = 0
    j = 0
    while i < len1 and j < len2:
        if nums1[i] == nums2[j]:
            count += 1
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return count

print sameElementsCount([1,2,3,4], [2,3])

如何使用函数式编程实现高阶函数，如（map/filter/reduce）。确保 算法复杂度为O（m+n）

Answer 1

在一些文章中给出的答案len(set(num1) & set(num2))写起来很快，但是它只需要基数就可以计算实际的集合交集。此外，它并不强调函数式编程风格的任何使用

以下行为与您的程序完全相同，但具有函数式编程风格： while循环被转换成一个递归函数，计数器被禁止放置到与列表匹配的模式中

def sameElementsCount(nums1, nums2):
    len1 = len(nums1)
    len2 = len(nums2)
    if len1 == 0 or len2 == 0:
        return 0
    elif nums1[0] == nums2[0]:
        return 1+sameElementsCount(nums1[1:],nums2[1:])
    elif nums1[0] < nums2[0]:
        return sameElementsCount(nums1[1:],nums2)
    else:
        return sameElementsCount(nums1,nums2[1:])

print sameElementsCount([1,2,3,4], [2,3])

Answer 2

可以使用set intersection:len(set(num1) & set(num2))