专栏首页SnailTyanLeetcode 350. Intersection of Two Arrays II

Leetcode 350. Intersection of Two Arrays II

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

1. Description

2. Solution

  • Version 1
class Solution:
    def intersect(self, nums1, nums2):
        nums1.sort()
        nums2.sort()
        m = len(nums1)
        n = len(nums2)
        i = 0
        j = 0
        result = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                result.append(nums1[i])
                i += 1
                j += 1
        return result
  • Version 2
class Solution:
    def intersect(self, nums1, nums2):
        stat = {}
        result = []

        for x in nums1:
            stat[x] = stat.get(x, 0) + 1

        for x in nums2:
            if x in stat and stat[x] > 0:
                result.append(x)
                stat[x] -= 1
        return result
  • Version 3
class Solution:
    def intersect(self, nums1, nums2):
        result = []
        nums2.sort()
        for num in nums1:
            index = binarySearch(nums2, num)
            if index is not None:
                result.append(num)
                nums2.pop(index)
        return result


def binarySearch(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        middle = (left + right) // 2
        if nums[middle] == target:
            return middle
        elif nums[middle] > target:
            right = middle - 1
        else:
            left = middle + 1
    return None

Reference

  1. https://leetcode.com/problems/intersection-of-two-arrays-ii/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 350. Intersection of Two Arrays II题目分析代码

    样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

    desperate633
  • leetcode-350-Intersection of Two Arrays II(求两个数组的交集)

    Given two arrays, write a function to compute their intersection.

    chenjx85
  • 每天一算:Intersection of Two Arrays II

    leetcode上第350号问题:Intersection of Two Arrays II

    五分钟学算法
  • Golang Leetcode 350. Intersection of Two Arrays II.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89089105

    anakinsun
  • 【LeetCode 136】 关关的刷题日记34 Intersection of Two Arrays II

    关关的刷题日记34 – Leetcode 350. Intersection of Two Arrays II 题目 Given two arrays, wri...

    WZEARW
  • LeetCode 350: 两个数组的交集 II Intersection of Two Arrays II

    Given two arrays, write a function to compute their intersection.

    爱写bug
  • leetcode-349-Intersection of Two Arrays

    chenjx85
  • Leetcode 349. Intersection of Two Arrays

    文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

    Tyan
  • 双指针,集合问题-LeetCode 344、345、347、349、350

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O...

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券