數(shù)據(jù)結(jié)構(gòu)（一）數(shù)組實(shí)現(xiàn)一個(gè)簡(jiǎn)單的ArrayList
數(shù)據(jù)結(jié)構(gòu)（二）鏈表實(shí)現(xiàn)LinkedList
數(shù)據(jù)結(jié)構(gòu)（三）用兩種方式簡(jiǎn)單實(shí)現(xiàn)棧
數(shù)據(jù)結(jié)構(gòu)（四）棧和隊(duì)列的簡(jiǎn)單應(yīng)用
數(shù)據(jù)結(jié)構(gòu)（五）用兩種方式簡(jiǎn)單實(shí)現(xiàn)隊(duì)列
數(shù)據(jù)結(jié)構(gòu)（六）二分搜索樹(Binary Search Tree)（上）
數(shù)據(jù)結(jié)構(gòu)（六）二分搜索樹(Binary Search Tree)（下）
數(shù)據(jù)結(jié)構(gòu)（七）兩種方式實(shí)現(xiàn)set
數(shù)據(jù)結(jié)構(gòu)（八）兩種方式實(shí)現(xiàn)map
數(shù)據(jù)結(jié)構(gòu)（九）set解決LeetCode349號(hào)問題
今天我們來看一下map解決LeetCode上第350題医增。題目如下
給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說明：
輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致悯蝉。
我們可以不考慮輸出結(jié)果的順序稀并。
下邊我們用map解決一下，源碼如下
import java.util.ArrayList;
import java.util.TreeMap;
public class Solution350 {
public int[] intersect(int[] nums1, int[] nums2) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int num: nums1){
if(!map.containsKey(num))
map.put(num, 1);
else
map.put(num, map.get(num) + 1);
}
ArrayList<Integer> res = new ArrayList<>();
for(int num: nums2){
if(map.containsKey(num)){
res.add(num);
map.put(num, map.get(num) - 1);
if(map.get(num) == 0)
map.remove(num);
}
}
int[] ret = new int[res.size()];
for(int i = 0 ; i < res.size() ; i ++)
ret[i] = res.get(i);
return ret;
}
}
這里我們創(chuàng)建了一個(gè)TreeMap蝴韭，我們把num作為key，這個(gè)元素出現(xiàn)的次數(shù)作為value乔煞，
- 首先我們把數(shù)組1的值存入到map中吁朦，這里我們判斷了一下這個(gè)map中有沒有這個(gè)key，如果有的話就把對(duì)應(yīng)的value+1渡贾，
- 其次我們遍歷數(shù)組2逗宜，如果包含這個(gè)key，那么就把這個(gè)元素存入到ArrayList中空骚，并且對(duì)應(yīng)的map里的value對(duì)應(yīng)減一纺讲，如果這個(gè)num對(duì)應(yīng)的value是0的話我們就把從map中刪掉。
- 最后我們把數(shù)據(jù)存到數(shù)組里就可以了囤屹。
好了這里就是我們簡(jiǎn)單的解決方法熬甚，如果大家有更好的方法歡迎在下邊評(píng)論。
更多精彩請(qǐng)關(guān)注公眾號(hào)及時(shí)接收
更多精彩請(qǐng)關(guān)注公眾號(hào)及時(shí)接收
