专栏首页desperate633LeetCode 349. Intersection of Two Arrays题目代码代码

LeetCode 349. Intersection of Two Arrays题目代码代码

Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, 2, 1] , nums2 = [2, 2] , return [2] . Note: Each element in the result must be unique. The result can be in any order. Subscribe to see which companies asked this question.

题目

返回两个数组的交

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

代码

这道题用了三种解法 解法一:推荐的解法,就是利用hashset的无重复元素,很容判断。先将数组一的元素塞进去,然后判断数组二的重复元素塞到另一个set,最后再转换成数组就好了 解法二:用的是排序和合并的算法。先排序好,然后将将元素合并就好了 解法三,用的是二分法,先将一个数组排序排好序,然后二分法查找是否重复,重复就加入。

代码

public class Solution {
    /**
     * @param nums1 an integer array
     * @param nums2 an integer array
     * @return an integer array
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        // Write your code here

        if (nums1 == null || nums2 == null) {
            return null;
        }
        
        HashSet<Integer> hash = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            hash.add(nums1[i]);
        }
        
        HashSet<Integer> resultHash = new HashSet<>();
        for (int i = 0; i < nums2.length; i++) {
            if (hash.contains(nums2[i]) && !resultHash.contains(nums2[i])) {
                resultHash.add(nums2[i]);
            }
        }
        
        int size = resultHash.size();
        int[] result = new int[size];
        int index = 0;
        for (Integer num : resultHash) {
            result[index++] = num;
        }
        
        return result;
    }
}
public class Solution {
    /**
     * @param nums1 an integer array
     * @param nums2 an integer array
     * @return an integer array
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        // Write your code here

        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i = 0, j = 0;
        int[] temp = new int[nums1.length];
        int index = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                if (index == 0 || temp[index - 1] != nums1[i]) {
                    temp[index++] = nums1[i];
                }
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        int[] result = new int[index];
        for (int k = 0; k < index; k++) {
            result[k] = temp[k];
        }
        
        return result;
    }
}
public class Solution {
    /**
     * @param nums1 an integer array
     * @param nums2 an integer array
     * @return an integer array
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        // Write your code here

         if (nums1 == null || nums2 == null) {
            return null;
        }
        
        HashSet<Integer> set = new HashSet<>();
        
        Arrays.sort(nums1);
        for (int i = 0; i < nums2.length; i++) {
            if (set.contains(nums2[i])) {
                continue;
            }
            if (binarySearch(nums1, nums2[i])) {
                set.add(nums2[i]);
            }
        }
        
        int[] result = new int[set.size()];
        int index = 0;
        for (Integer num : set) {
            result[index++] = num;
        }
        
        return result;
    }
    
    private boolean binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] == target) {
            return true;
        }
        if (nums[end] == target) {
            return true;
        }
        
        return false;
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    desperate633
  • LintCode 爬楼梯题目分析代码小结

    假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

    desperate633
  • LintCode 余弦相似度题目分析代码

    给你两个相同大小的向量 A B,求出他们的余弦相似度 返回2.0000 如果余弦相似不合法 (比如 A = [0] B = [0]).

    desperate633
  • LeetCode100|两个数组的交集II

    这是自己目前输出的leetcode第100篇题解慢一点,才能更快,98道leetcode,也是自己坚持过程中一个结果,感谢周围的人和自己,这里道一句谢谢吧,没有...

    后端Coder
  • 【leetcode刷题】T43-两个数组的交集

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

    木又AI帮
  • LeetCode:4_Median of Two Sorted Arrays | 求两个排序数组的中位数 | Hard

    题目: There are two sorted arrays nums1 and nums2 of size m and n respectively. F...

    CloudDeveloper
  • leetcode373. Find K Pairs with Smallest Sums

    两个单调递增的整数数组,现分别从数组1和数组2中取一个数字构成数对,求找到k个和最小的数对。

    眯眯眼的猫头鹰
  • 两个数组的交集 II

    就相当于是数学集合求交集,很容易想到的就是双指针扫描比较判断是否存入结果。对于这样的方式就选择先排序再比较。

    木瓜煲鸡脚
  • 每日打卡 373. 查找和最小的K对数字

    题目告诉你 2个有序数组,求top k 不是 从2个有序数组获取一个记录就可以了。

    程序员小王
  • Leetcode No.4 寻找两个正序数组的中位数

    请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

    week

扫码关注云+社区

领取腾讯云代金券