解題報告 ? ?- Copy

LeetCode 兩個數組的交集II

@TOC

題目描述

?給你兩個整數數組 nums1 和 nums2 ，請你以數組形式返回兩數組的交集。返回結果中每個元素出現的次數，應與元素在兩個數組中都出現的次數一致（如果出現次數不一致，則考慮取較小值）?？梢圆豢紤]輸出結果的順序。

兩個數組的交集II
示例：

1輸入：nums1?=?[1,2,2,1],?nums2?=?[2,2]?輸出：[2,2]


提示：

11?<=?nums1.length,?nums2.length?<=?1000
20?<=?nums1[i],?nums2[i]?<=?1000
3


一、解題關鍵詞

1返回數組?出現次數?考慮取比較小的數值


二、解題報告

1.思路分析

1. 兩個數組肯定需要遍歷兩次，

2. 注意控制遍歷順序，比較稍微短些到數組（需要取交集）

3. 記錄當前數字 +出現次數

4. 兩次循環(huán) 取交集

2.時間復雜度

3.代碼示例

1class?Solution?{
2????//二分思想
3????public?int[]?intersect(int[]?nums1,?int[]?nums2)?{
4????????int?len1?=?nums1.length;
5????????int?len2?=?nums2.length;
6
7????????if?(len1>?len2){
8????????????return?intersect(nums2,nums1);
9????????}
10????????Map<Integer,Integer>?map?=?new?HashMap<Integer,Integer>();
11
12????????for?(int?num:nums1){
13????????????int?count?=?map.getOrDefault(num,0)?+?1;
14????????????map.put(num,count);
15????????}
16????????int?[]?resNum?=?new??int[len1];
17????????int?index?=?0;
18
19????????for?(int?num?:?nums2){
20????????????int?count?=?map.getOrDefault(num,0);
21????????????if?(count?>?0){
22????????????????resNum[index++]?=?num;
23????????????????count?--;
24????????????????if?(count?>?0){
25????????????????????map.put(num,count);
26????????????????}else{
27????????????????????map.remove(num);
28????????????????}
29????????????}
30????????}
31????????return?Arrays.copyOfRange(resNum,??0,index);
32????}
33}


4.知識點

1map這個數據結構遍歷方式有四種
21、keyset
32、entrySet（推薦）
43、iterator
54、map.values(