编程知识 cdmana.com

【算法千題案例】️每日LeetCode打卡️——53.兩個數組的交集 II

請添加圖片描述


前言

算法題
  • 每天打卡一道算法題,既是一個學習過程,又是一個分享的過程
  • 提示:本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
  • 要保持一個每天都在學習的狀態,讓我們一起努力成為算法大神吧🧐!
  • 今天是力扣算法題持續打卡第53天!
算法題

原題樣例:兩個數組的交集

給定兩個數組,編寫一個函數來計算它們的交集。

示例:

輸入:nums1 = [1,2,2,1], nums2 = [2,2]
輸出:[2]

示例 2:

輸入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出:[9,4]

說明:

  • 輸出結果中每個元素出現的次數,應與元素在兩個數組中出現次數的最小值一致。
  • 我們可以不考慮輸出結果的順序。

C#方法:字典

使用Dictionary字典操作,先把第一個數組遍曆進字典,然後再同第二個數組做判定即可!

代碼:

public class Solution {
    
    public int[] Intersect(int[] nums1, int[] nums2) {
    
        var dic = new Dictionary<int,int>();
        List<int> list = new List<int>();
        foreach(int n in nums1)
        {
    
            if(dic.ContainsKey(n))
                dic[n]++;
            else
                dic.Add(n,1);
        }
        foreach(int n in nums2)
        {
    
            if(dic.ContainsKey(n)&&dic[n]>0)
            {
    
                dic[n]--;
                list.Add(n);
            }
        }
        return list.ToArray();
    }
}

執行結果

通過
執行用時:128 ms,在所有 C# 提交中擊敗了99.61%用戶
內存消耗:40.4 MB,在所有 C# 提交中擊敗了5.26%的用戶

Java 方法:哈希

思路解析

  • 由於同一個數字在兩個數組中都可能出現多次,因此需要用哈希錶存儲每個數字出現的次數。

  • 對於一個數字,其在交集中出現的次數等於該數字在兩個數組中出現次數的最小值。

  • 首先遍曆第一個數組,並在哈希錶中記錄第一個數組中的每個數字以及對應出現的次數,然後遍曆第二個數組,對於第二個數組中的每個數字,如果在哈希錶中存在這個數字,則將該數字添加到答案,並减少哈希錶中該數字出現的次數。

  • 為了降低空間複雜度,首先遍曆較短的數組並在哈希錶中記錄每個數字以及對應出現的次數,然後遍曆較長的數組得到交集。

請添加圖片描述

代碼:

class Solution {
    
    public int[] intersect(int[] nums1, int[] nums2) {
    
        if (nums1.length > nums2.length) {
    
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
    
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
    
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
    
                intersection[index++] = num;
                count--;
                if (count > 0) {
    
                    map.put(num, count);
                } else {
    
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

執行結果

通過
執行用時:3 ms,在所有 Java  提交中擊敗了45.01%的用戶
內存消耗:38.8 MB,在所有 Java 提交中擊敗了5.86%的用戶

複雜度分析

時間複雜度:O( m+n )
空間複雜度:O( m+n ) 

Java方法二:排序 + 雙指針

  • 如果兩個數組是有序的,則可以使用雙指針的方法得到兩個數組的交集。

  • 首先對兩個數組進行排序,然後使用兩個指針遍曆兩個數組。

  • 可以預見的是加入答案的數組的元素一定是遞增的,為了保證加入元素的唯一性,我們需要額外記錄變量 pre 錶示上一次加入答案數組的元素。

  • 初始時,兩個指針分別指向兩個數組的頭部。每

  • 次比較兩個指針指向的兩個數組中的數字,如果兩個數字不相等,則將指向較小數字的指針右移一比特,如果兩個數字相等,且該數字不等於pre,將該數字添加到答案並更新 pre 變量,同時將兩個指針都右移一比特。

  • 當至少有一個指針超出數組範圍時,遍曆結束。

代碼

class Solution {
    
    public int[] intersect(int[] nums1, int[] nums2) {
    
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
    
            if (nums1[index1] < nums2[index2]) {
    
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
    
                index2++;
            } else {
    
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

執行結果

通過
執行用時:2 ms,在所有 Java  提交中擊敗了77.89%的用戶
內存消耗:38.8 MB,在所有 Java 提交中擊敗了16.56%的用戶

複雜度分析

時間複雜度:O( mlogm + nlogn )
空間複雜度:O( logm + logn )

總結

  • 今天是力扣算法題打卡的第五十三天!
  • 文章采用 C#Java 兩種編程語言進行解題
  • 一些方法也是參考力扣大神寫的,也是邊學習邊分享,再次感謝算法大佬們
  • 那今天的算法題分享到此結束啦,明天再見!
    請添加圖片描述

版权声明
本文为[呆呆敲代碼的小Y]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211014060755147u.html

Scroll to Top