LeetCode题解(1213):三个有序数组的交集(Python)
发布日期:2021-06-29 20:09:49 浏览次数:2 分类:技术文章

本文共 781 字,大约阅读时间需要 2 分钟。

题目:(简单)

标签:哈希表、二分查找、双指针

解法 时间复杂度 空间复杂度 执行用时
Ans 1 (Python) O ( N l o g N ) O(NlogN) O(NlogN) O ( 1 ) O(1) O(1) 116ms (37.02%)
Ans 2 (Python)
Ans 3 (Python)

解法一(二分查找):

class Solution:    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:        s1, s2, s3 = len(arr1), len(arr2), len(arr3)        ans = []        i1, i2, i3 = 0, 0, 0        while i1 < s1 and i2 < s2 and i3 < s3:            if arr1[i1] == arr2[i2] == arr3[i3]:                ans.append(arr1[i1])                i1 += 1            else:                v = max(arr1[i1], arr2[i2], arr3[i3])                i1 = bisect.bisect_left(arr1, v, lo=i1)                i2 = bisect.bisect_left(arr2, v, lo=i2)                i3 = bisect.bisect_left(arr3, v, lo=i3)        return ans

转载地址:https://dataartist.blog.csdn.net/article/details/109848620 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:LeetCode题解(1224):最大相等频率(Python)
下一篇:LeetCode题解(1198):找出所有行中最小公共元素(Python)

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年04月07日 06时39分35秒