[LeetCode] 350. Intersection of Two Arrays II 解題思路 (Easy)

這題需要判斷兩個陣列共通的數字有哪些，返回一個結果陣列。

LeetCode 題目連結

 

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

 

題目

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Accept 作法

這題利用 HashSet 去判斷重複的部分。


Runtime: 9 ms
Memory: 39.7 MB

Java 程式碼

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        HashSet<Integer> map =new HashSet<Integer>();
        for(int i = 0;i<nums1.length;i++){
            for(int j = 0;j<nums2.length;j++){
                if(nums1[i] == nums2[j] && !map.contains(j)){
                    list.add(nums1[i]);
                    map.add(j);
                    break;
                }
            }
        }
        
        int[] resultArray = new int[list.size()];
        for(int i = 0;i<resultArray.length;i++){
            resultArray[i] = list.get(i);
        }
        return resultArray;
        
    }
}

再來第二種解法是 Two Pointer 的解法。

Java 程式碼

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        int cursor = 0;
        int cursor2 = 0;
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        while(cursor < nums1.length && cursor2 < nums2.length){
            if(nums1[cursor] == nums2[cursor2]){
                list.add(nums1[cursor]);
                cursor ++;
                cursor2 ++;
            }else if(nums1[cursor] > nums2[cursor2]){
                cursor2 ++;
            }else if(nums1[cursor] < nums2[cursor2]){
                cursor ++;
            }
            
        }
        
        int[] resultArray = new int[list.size()];
        for(int i = 0;i<resultArray.length;i++){
            resultArray[i] = list.get(i);
        }
        return resultArray;
        
        
    }
}

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題