【LeetCode题解】349_两个数组的交集

【LeetCode题解】349_两个数组的交集

描述

给定两个数组，编写一个函数来计算它们的交集。

示例1：

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

输出：[2]

示例2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出：[9,4]

说明：

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

方法一：两个哈希表

Java 实现

import java.util.Set;

import java.util.HashSet;

class Solution {

    public int[] intersection(int[] nums1, int[] nums2) {

        Set<Integer> set1 = new HashSet<>();

        Set<Integer> set2 = new HashSet<>();

        for (int num : nums1) {

            set1.add(num);

        }

        for (int num : nums2) {

            if (set1.contains(num)) {

                set2.add(num);

            }

        }

        int[] ret = new int[set2.size()];

        int i = 0;

        for (int num : set2) {

            ret[i++] = num;

        }

        return ret;

    }

}

// Runtime: 2 ms

// Your runtime beats 98.84 % of java submissions.

复杂度分析：

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

类似的 Java 实现

import java.util.List;

import java.util.ArrayList;

import java.util.Set;

import java.util.HashSet;

class Solution {

    public int[] intersection(int[] nums1, int[] nums2) {

        Set<Integer> set = new HashSet<>();

        for (int num : nums1) {

            set.add(num);

        }

        List<Integer> list = new ArrayList<>();

        for (int num : nums2) {

            if (set.contains(num)) {

                list.add(num);

                set.remove(num);

            }

        }

        int[] ret = new int[list.size()];

        for (int i = 0; i < list.size(); ++i) {

            ret[i] = list.get(i);

        }

        return ret;

    }

}

Python 实现

class Solution:

    def intersection(self, nums1, nums2):

        """

        :type nums1: List[int]

        :type nums2: List[int]

        :rtype: List[int]

        """

        return list(set(nums1) & set(nums2))

复杂度分析同上。

类似的 Python 实现

class Solution:

    def intersection(self, nums1, nums2):

        """

        :type nums1: List[int]

        :type nums2: List[int]

        :rtype: List[int]

        """

        if len(nums1) == 0 or len(nums2) == 0:

        	return []

        ret = []

        s1 = set(nums1)

        s2 = set(nums2)

        for num in s1:

        	if num in s2:

        		ret.append(num)

		return ret

# Runtime: 36 ms

# Your runtime beats 100.00 % of python3 submissions.

复杂度分析同上。

方法二：双指针

Java 实现

import java.util.Arrays;

import java.util.Set;

import java.util.HashSet;

class Solution {

    public int[] intersection(int[] nums1, int[] nums2) {

        Arrays.sort(nums1);

        Arrays.sort(nums2);

        Set<Integer> set = new HashSet<>();

        int i = 0, j= 0;

        while (i < nums1.length && j < nums2.length) {

            if (nums1[i] < nums2[j]) {

                ++i;

            } else if (nums1[i] > nums2[j]) {

                ++j;

            } else {

                set.add(nums1[i]);

                ++i;

                ++j;

            }

        }

        int[] ret = new int[set.size()];

        int k = 0;

        for (int num : set) {

            ret[k++] = num;

        }

        return ret;

    }

}

// Runtime: 3 ms

// Your runtime beats 90.80 % of java submissions.

复杂度分析：

时间复杂度：\(O(nlog(n))\)
空间复杂度：\(O(n)\)

方法三：二分查找

Java 实现

import java.util.Arrays;

import java.util.Set;

import java.util.HashSet;

class Solution {

    public int[] intersection(int[] nums1, int[] nums2) {

        Arrays.sort(nums2);

        Set<Integer> set = new HashSet<>();

        for (int num : nums1) {

            if (binarySearch(nums2, num)) {

                set.add(num);

            }

        }

        int[] ret = new int[set.size()];

        int i = 0;

        for (int num : set) {

            ret[i++] = num;

        }

        return ret;

    }

    private boolean binarySearch(int[] nums, int target) {

        int low = 0;

        int high = nums.length - 1;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            if (nums[mid] == target) {

                return true;

            } else if (nums[mid] < target) {

                low = mid + 1;

            } else {

                high = mid - 1;

            }

        }

        return false;

    }

}

// Runtime: 6 ms

// Your runtime beats 23.44 % of java submissions.

复杂度分析：

时间复杂度：\(O(nlog(n))\)
空间复杂度：\(O(n)\)

方法四

Java 实现

class Solution {

    public int[] intersection(int[] nums1, int[] nums2) {

        // 确定数组 nums1 的取值范围

		int max = Integer.MIN_VALUE;

		int min = Integer.MAX_VALUE;

		for (int num : nums1) {

			if (num > max) {

				max = num;

			}

			if (num < min) {

				min = num;

			}

		}

		boolean[] arr = new boolean[max - min + 1];

		for (int num : nums1) {

			arr[num - min] = true;

		}

		// 判断数组 nums2 中的数是否在数组 nums1 中存在，

		// 如果存在保存在数组 tmp 中

		int[] tmp = new int[max - min + 1];

		int idx = 0;

		for (int num : nums2) {

			if (num >= min && num <= max && arr[num - min]) {

				tmp[idx++] = num;

				arr[num- min] = false;

			}

		}

		// 返回结果

		int[] ret = new int[idx];

		for (int i = 0; i < idx; i++) {

			ret[i] = tmp[i];

		}

		return ret;

    }

}

// Runtime: 0 ms

// Your runtime beats 100.00 % of java submissions.

复杂度分析：

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

巴特西

【LeetCode题解】349_两个数组的交集

【LeetCode题解】349_两个数组的交集

描述

方法一：两个哈希表

Java 实现

类似的 Java 实现

Python 实现

类似的 Python 实现

方法二：双指针

Java 实现

方法三：二分查找

Java 实现

方法四

Java 实现

最新文章

热门文章