[LeetCode] 350. Intersection of Two Arrays II

https://leetcode.com/problems/intersection-of-two-arrays-ii/description/

leetcode - Intersection of Two Arrays II

문제 유형 : 그리디, 정렬

문제 난이도 : Easy

 

문제

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.

 

두 정수 nums1과 nums2가 주어진다. 두 배열의 합집합을 구하시오.

요소는 여러 번 나올 수 있고, 순서는 상관없습니다.

 

풀이

두 배열을 정렬하고, 두 배열을 가리키는 인덱스를 하나씩 만든다.

둘다 인덱스 0부터 해서 같으면 둘다 같이 증가하고 ans에 추가, 아니라면 더 작은 쪽의 인덱스를 키운다.

두 배열의 순회가 끝나면, ans배열을 반환.

 

코드

C++

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        int i = 0, j = 0;
        while(i < nums1.size() && j < nums2.size()) {
            if(nums1[i] == nums2[j]) {
                ans.push_back(nums1[i]);
                i++;
                j++;
            } else if(nums1[i] > nums2[j]) {
                j++;
            } else {
                i++;
            }
        }

        return ans;
    }
};