专栏首页眯眯眼猫头鹰的小树杈leetcode349. Intersection of Two Arrays

leetcode349. 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.

找出两个无序数组中重合的值。

思路一:排序

思路一模仿了归并排序的merge部分。先将两个数组分别排序,排序完成之后再用两个指针分别比较两个数组的值。如果两个指针指向的值相同,则向结果集中添加该元素并且同时将两个指针向前推进。否则指向的值较小的那个指针向前推进。

    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> nums3 = new ArrayList<Integer>();
            int i=0, j=0;
        while(i<nums1.length && j<nums2.length){
            if(nums1[i]==nums2[j])
            {
                if(!nums3.contains(nums1[i]))
                     nums3.add(nums1[i]);
                i++;
                j++;
             }
            else if(nums1[i]>nums2[j])
                j++;
            else
                i++;
        }
        int[] arr = new int[nums3.size()];
        for(int k=0;k<nums3.size();k++)
            arr[k]=nums3.get(k);
        return arr;
    }

受排序算法影响,该方法的时间复杂度为O(nlgn)

思路二:建立索引

一方面排序对时间的消耗很大,另一方面数组中如果出现重复的值,也意味着大量无效的遍历。那么如何才能够在不便利的情况下获取二者的重合值。答案是为其中一个数组通过建立索引的方式排序。 什么叫建立索引的方式排序?这是指先获取数组中的最大值max和最小值min,然后将整数数组转化为一个长度为max-min+1的布尔型数组,布尔型数组i位置上的值代表原整数数组中是否存在数组i+min。如[1,6,7,0]对应的布尔型数组为[true,true,false,false,false,false,true,true]。这实际上是一种空间换时间的做法。通过这种方式,我们就可以在O(n)的时间复杂度内完成搜索。

    public int[] intersection2(int[] nums1, int[] nums2){
        if(nums1==null || nums2==null || nums1.length == 0 || nums2.length == 0){
            return new int[0];
        }
        int max = nums1[0], min = nums1[0];
        for(int n : nums1){
            if(n > max) max = n;
            else if(n < min) min = n;
        }
        
        boolean[] index = new boolean[max - min + 1];
        for(int n : nums1){
            index[n - min] = true;
        }
        
        int count = 0;
        int[] tmp = new int[Math.min(nums1.length, nums2.length)];
        for(int n : nums2){
            if(n>=min && n<=max && index[n-min]){
                tmp[count++] = n;
                index[n-min] =false;
            }
        }
        return count == tmp.length ? tmp : Arrays.copyOf(tmp, count);
    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode373. Find K Pairs with Smallest Sums

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

    眯眯眼的猫头鹰
  • leetcode523. Continuous Subarray Sum

    Given a list of non-negative numbers and a target integer k, write a function to...

    眯眯眼的猫头鹰
  • leetcode365. Water and Jug Problem

    假设现在有两个杯子,每个杯子分别最多可以装x和y升水,假设现在水的供应量是无限的,问是否有可能用这两个杯子共同承装z升水,可以用两个杯子执行的操作如下:

    眯眯眼的猫头鹰
  • 寻找两个有序数组的中位数

    https://leetcode.com/problems/median-of-two-sorted-arrays/

    lucifer210
  • leecode刷题(6)-- 两个数组的交集II

    我们可以用遍历穷举的方法,但是时间复杂度肯定很高。不妨换个思路:先将数组递增排序,排序之后将两个数组同时遍历(定义两个数组的脚本变量,初始值为0,向后遍历),比...

    希希里之海
  • 专访印度最大电商Flipkart CEO

    印度的电商市场正进入快速发展阶段。今年7月,印度最大电商网站Flipkart宣布获得一轮10亿美元融资,总估值达70亿美元,成全球估值最高的非上市互联网公司之...

    腾讯研究院
  • 算法细节系列(8):4. Median of Two Sorted Arrays

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 职能部门的需求

    用户2025931
  • 如何实现更换Jupyter Notebook内核Python版本

    我使用anaconda安装的python3.6.3,并且自己建立一个虚拟环境,虚拟环境下的python版本也是3.6.3,Jupyter Notebook的内核...

    砸漏
  • plugins/python/uwsgi_python.h:2:20: fatal error: Python.h: No such file or directory

    plugins/python/uwsgi_python.h:2:20: fatal error: Python.h: No such file or direc...

    yaohong

扫码关注云+社区

领取腾讯云代金券