문제
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
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] Explanation: [9,4] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000
Follow up:
What if the given array is already sorted? How would you optimize your algorithm? What if nums1’s size is small compared to nums2’s size? Which algorithm is better? What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
내 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
//Runtime: 3 ms
//Memory Usage: 43.5 MB
//solution: sort array first and use two pointers to compare
Arrays.sort(nums1);
Arrays.sort(nums2);
int nums1Index = 0;
int nums2Index = 0;
List<Integer> answerList = new ArrayList<>();
while(nums1Index < nums1.length && nums2Index < nums2.length){
if(nums1[nums1Index] == nums2[nums2Index]){ // if it has the same value, save and move forward both pointers
answerList.add(nums1[nums1Index]);
++nums1Index;
++nums2Index;
}else if(nums1[nums1Index]>nums2[nums2Index]){ // if one array's value is greater that another, move pointer forward, because it is not worth to compare later values (since it is sorted)
++nums2Index;
}else if(nums1[nums1Index]<nums2[nums2Index]){
++nums1Index;
}
}
int[] answer = new int[answerList.size()];
//list to array
for(int i=0; i<answer.length; i++){
answer[i] = answerList.get(i);
}
return answer;
}
}