90일 (Minimum Common Value) twoPointers

Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1.

Note that an integer is said to be common to nums1 and nums2 if both arrays have at least one occurrence of that integer.

 

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Explanation: The smallest element common to both arrays is 2, so we return 2.

Example 2:

Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
Output: 2
Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.

 

Constraints:

• 1 <= nums1.length, nums2.length <= 10^5
• 1 <= nums1[i], nums2[j] <= 10^9
• Both nums1 and nums2 are sorted in non-decreasing order.

 

- 접근방법

간단하게 nums1과 nums2의 공통된 값 중 최솟값을 리턴하면 된다.

두 배열 모두 내림차순 정렬이 아니다.(하지만 오름차순 정렬이다.)

 

 

- 코드 (13ms), set

class Solution {
    public int getCommon(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();

        for(int i : nums1) set.add(i);

        for(int i : nums2) {
            if(set.contains(i)) return i;
        }

        return -1;
    }
}

 

Hashset을 이용한 방법이다.

배열은 오름차순이므로 nums1을 set에 저장하고, nums2를 처음부터 비교하여 같은 값을 리턴하면 된다.

 

 

- 코드 (1ms), two pointers

class Solution {
    public int getCommon(int[] nums1, int[] nums2) {
        int ptr1 = 0;
        int ptr2 = 0;

        while(ptr1 < nums1.length && ptr2 < nums2.length) {
            int num1 = nums1[ptr1];
            int num2 = nums2[ptr2];

            if(num1 > num2) ptr2++;
            else if(num1 < num2) ptr1++;
            else return num1;
        }

        return -1;
    }
}

 

양쪽 배열 포인터를 이용하여 양쪽 배열이 같아질때까지 비교하였다.

또한 중복되서 사용되는 nums1[ptr1]과 nums2[ptr2]를 따로 변수로 지정하여 사용하므로 2ms에서 1ms까지 시간단축이 되었다.

 

매우 쉽고 간단한 문제이지만 

이중for문으로 접근할 때 28ms

set 하나로 접근할 때 13ms

포인터로 접근할 때 1ms

 

ms차이로 보면 큰 차이가 없지만 1시간 13시간 28시간으로 보면 어마어마하다.

접근하기는 쉬운 문제이지만 방법에 따라 속도차이가 심하게 나며, 특정한 문제에 대한 접근방법이 아닌 일반적인 접근방법을 생각하게 하므로 따봉 비율이 높은 문제인 것 같다.

 

 

 

 

https://leetcode.com/problems/minimum-common-value/

Minimum Common Value - LeetCode