leetcode349. Intersection of Two Arrays

only_do 發布于2019-08-16 12:41 / 474人閱讀

摘要：題目要求找出兩個無序數組中重合的值。先將兩個數組分別排序，排序完成之后再用兩個指針分別比較兩個數組的值。如果兩個指針指向的值相同，則向結果集中添加該元素并且同時將兩個指針向前推進。答案是為其中一個數組通過建立索引的方式排序。

題目要求

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 nums3 = new ArrayList();
            int i=0, j=0;
        while(inums2[j])
                j++;
            else
                i++;
        }
        int[] arr = new int[nums3.size()];
        for(int k=0;k
受排序算法影響，該方法的時間復雜度為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);
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Intersection Arrays Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71533.html

LeetCode 349. Intersection of Two Arrays

摘要：描述給定兩個數組，編寫一個函數來計算它們的交集。示例輸入輸出示例輸入輸出說明輸出結果中的每個元素一定是唯一的。我們可以不考慮輸出結果的順序。思路內置集合可以完成交運算，然后再轉換為即可。何睿何睿內置集合運算源代碼文件在這里。 Description Given two arrays, write a function to compute their intersection. Exa...

RyanQ 2019-07-31 10:16 評論0 收藏0
Leetcode PHP題解--D72 349. Intersection of Two Array

摘要：題目鏈接題目分析返回給定兩個數組的交集。思路這既然不是自己實現的話，直接用就完事了。最終代碼若覺得本文章對你有用，歡迎用愛發電資助。 D72 349. Intersection of Two Arrays 題目鏈接 349. Intersection of Two Arrays 題目分析返回給定兩個數組的交集。思路這既然不是自己實現的話，直接用array_intersect就完事...

sixleaves 2019-07-01 12:49 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[LintCode/LeetCode] Intersection of Two Arrays I &

摘要：先想到的是，其實也可以，只是需要在遍歷的時候，添加到數組中的數要掉，略微麻煩了一點。在里跑的時候，也要快一點。另一種類似做法的就快的多了。如果是找出所有包括重復的截距呢 Problem Given two arrays, write a function to compute their intersection. Notice Each element in the result m...

enda 2019-08-14 14:03 評論0 收藏0