Common Elements in Two Sorted Arrays (Java)

Write a function that returns the common elements (as an array) between two sorted arrays of integers (ascending order).

Example: The common elements between [1, 3, 4, 6, 7, 9] and [1, 2, 4, 5, 9, 10] are [1, 4, 9].

풀이

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

public class CE {

    public static void main(String[] args) {

        // NOTE: The following input values are used for testing your solution.

        int[] array1A = {1, 3, 4, 6, 7, 9};

        int[] array2A = {1, 2, 4, 5, 9, 10};

        // commonElements(array1A, array2A) should return [1, 4, 9] (an array).

        int[] array1B = {1, 2, 9, 10, 11, 12};

        int[] array2B = {0, 1, 2, 3, 4, 5, 8, 9, 10, 12, 14, 15};

        // commonElements(array1B, array2B) should return [1, 2, 9, 10, 12] (an array).

        int[] array1C = {0, 1, 2, 3, 4, 5};

        int[] array2C = {6, 7, 8, 9, 10, 11};

        // common_elements(array1C, array2C) should return [] (an empty array).

    }

    // Implement your solution below.

    // NOTE: Remember to return an Integer array, not an int array.

    public static Integer[] commonElements(int[] array1, int[] array2) {

        Integer[] resultInArray = new Integer[0];

            List<Integer> tempList = new ArrayList<>();

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i : array1) {

            map.put(i, i);

        }

        for (int i : array2) {

            if (map.containsKey(i)) {

                tempList.add(i);

            }

        }

        resultInArray = new Integer[tempList.size()];

        for (int i = 0; i < tempList.size(); i++) {

            resultInArray[i] = tempList.get(i);

        }

        return resultInArray;

    }

}

해당 강사가 한 방법은

1. 각 배열의 index를 비교를 한다

2. 비교 결과 같으면 그 값을 리스트에 넣고, 각 배열의 index 는 모두 +1씩 이동

3. 비교 결과 다른경우 (한쪽이 크고 한쪽은 작음), 작은 쪽의 index 만 1 증가해서 다시 비교

4. 각 배열의 index가 각 배열의 length 만큼 되면 while 종료