Intersection of Two Arrays

,

Problem

Given two arrays, write a function to compute their intersection.

Note

  • Each element in the result must be unique
  • The result can be in any order.

Example 1

1
2

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2

1
2

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

My Answer 1

  • nums1, nums2 배열을 오름차순으로 정렬 한다.
  • 두개의 배열중 갯수가 적은 것을 기준으로 반복 돌면서 nums2에서 일치 하는것을 찾는다.
  • 만약 이전 반복에서 체크했던 값과 같을경우는 넘어간다.
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
41
42
43
44
45
46
47
48
49
50

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] result;
        if ( nums1.length < nums2.length ) {
            result = intersectionArray(nums1, nums2);
        } else {
            result = intersectionArray(nums2, nums1);
        }
        
        return result;
    }
    
    int[] intersectionArray(int[] nums1, int[] nums2) {
        List<Integer> result = new ArrayList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        for(int i=0; i< nums1.length;i++) {
            if ( i > 0 && nums1[i] == nums1[i-1])
                continue;
            
            int l=0;
            int r=nums2.length-1;
            
            while(l < r ) {
                int mid = (l+r)/2;
                if ( nums2[mid] == nums1[i]) {
                    l = mid;
                    break;
                }
                
                if ( nums2[mid] < nums1[i]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            
            if ( nums2[l] == nums1[i]) {
                result.add(nums1[i]);
            }
        }
        
        int[] array = new int[result.size()];
        int i = 0;
        for(int x : result)
            array[i++] = x;
        return array;
    }
}

My Answer 2

  • i,j,k를 각각 nums1의 index, nums2의 index, temp_res의 index이자 결과 리스트에 넣을 index 로 활용하자.
  • nums1, nums2 배열을 오름차순으로 정렬 한다.
  • nums1[i] == nums2[j]일 경우, 결과 리스트에 넣을 기본 조건에 만족 한다. 추가로, k가 0보다 클땐 temp_res[k-1]과 다른지 확인 필요하다. 중첩된 값을 결과 리스트에 넣을 수 없기 때문에.
  • nums1[i] <= nums2 일땐 i를 증가 시키고, nums1[i] >= nums2[j] 일땐 j를 증가 시키자.
  • 최종적으로 temp_res에 있는 값들중 k만큼만 새로운 결과 배열에 옮겨 담으면 된다.
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

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int i=0;
        int j=0;
        int k=0;
        int[] temp_res = new int[nums1.length];
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        while(i < nums1.length && j < nums2.length ) {
            if ( nums1[i] == nums2[j] && (k == 0 || (k > 0 && temp_res[k-1] != nums1[i])) ) {
                temp_res[k++] = nums1[i];                
                i++;
                j++;
            } else if ( nums1[i] <= nums2[j]) {            
                i++;
            } else if ( nums1[i] >= nums2[j]) {
                j++;
            }
        }
        
        int[] res = new int[k];
        for(int t=0;t<k;t++) {
            res[t] = temp_res[t];
        }
        
        return res;        
    }    
}

My Answer ( Use HashSet )

  • nums1을 순회하면서 HashSet에 넣자.
  • nums2를 순회하면서 중복된 값이 있는지 확인하고, 중복된 값이 있다면, nums1의 앞에서 부터 덮어 쓰면서 중복된 값의 갯수를 k에 저장.
  • nums1의 0~k-1의 값이 최종 결과
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

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> hashSet = new HashSet<>();
        
        Arrays.sort(nums2);
        
        int i=0;
        while(i < nums1.length ) {
            if ( !hashSet.contains(nums1[i]) )
                hashSet.add(nums1[i]);            
            i++;
        }
        
        i=0;
        int k=0;
        while(i < nums2.length ) {
            if ( hashSet.contains(nums2[i])) {
                if ( k == 0 || nums1[k-1] != nums2[i]) {
                    nums1[k++] = nums2[i];        
                }
            }
            i++;
        }
        
        int[] result = new int[k];
        System.arraycopy(nums1, 0, result, 0, k);
        
        return result;
    }    
}

참고