題目
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說明：
輸出結果中每個元素出現(xiàn)的次數(shù)靶病，應與元素在兩個數(shù)組中出現(xiàn)的次數(shù)一致口予。
我們可以不考慮輸出結果的順序。
進階:
如果給定的數(shù)組已經(jīng)排好序呢沪停？你將如何優(yōu)化你的算法裳涛？
如果 nums1 的大小比 nums2 小很多端三，哪種方法更優(yōu)鹃彻？
如果 nums2 的元素存儲在磁盤上蛛株，磁盤內(nèi)存是有限的，并且你不能一次加載所有的元素到內(nèi)存中谨履，你該怎么辦笋粟？
思路
- 使用Map記錄nums1中的數(shù)字情況，Key為值绿淋，Value為出現(xiàn)的次數(shù)
然后遍歷nums2中的每個數(shù)值num：
若map.containsKey(num) && map.get(num) > 0躬它，則將該值記錄至List中东涡，次數(shù)-1；
否則遍歷下一個
時間復雜度O（n）
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
for(int num: nums1)
if(!record.containsKey(num))
record.put(num, 1);
else
record.put(num, record.get(num) + 1);
ArrayList<Integer> result = new ArrayList<Integer>();
for(int num: nums2)
if(record.containsKey(num) && record.get(num) > 0){
result.add(num);
record.put(num, record.get(num) - 1);
}
int[] ret = new int[result.size()];
int index = 0;
for(Integer num: result)
ret[index++] = num;
return ret;
}
}
- 對數(shù)組排序组贺，然后使用雙指針遍歷兩個數(shù)組
時間復雜度O（nlogn）
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> list = new ArrayList<>();
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0;
int j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
list.add(nums1[i]);
i++;
j++;
}
}
int[] result = new int[list.size()];
int k = 0;
for (Integer num : list) {
result[k++] = num;
}
return result;
}
}
