---
# System prepended metadata

title: 'Leetcode [No. 349] Intersection of two arrays (EASY) 解題心得'
tags: [leetcode]

---

# Leetcode [No. 349] Intersection of two arrays (EASY) 解題心得

+ Daily Challenge solved on 2024/03/10 

## 題目

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

## 思路

+ 這個解法就是先用sort確保兩個陣列都是non-decreasing的陣列
+ 再用two ptr去逐一比較就結束了

```c++=
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int ptr1 = 0; int ptr2 = 0;
        while(ptr1 < nums1.size() && ptr2 < nums2.size())
        {
            while(ptr1 < nums1.size()-1 && nums1[ptr1] == nums1[ptr1+1]) // to the right most same int
            {
                ptr1++;
            }
            // cout << "ptr1 = " << ptr1 << endl;
            while(ptr2 < nums2.size()-1 && nums2[ptr2] == nums2[ptr2+1]) // to the right most same int
            {
                ptr2++;
            }
            // cout << "ptr2 = " << ptr2 << endl;
            if(nums1[ptr1] == nums2[ptr2])
            {
                res.emplace_back(nums1[ptr1]);
                ptr1++;
                ptr2++;
            }
            else if (nums1[ptr1] > nums2[ptr2])
            {
                ptr2++;
            }
            else 
            {
                ptr1++;
            }
        }
        return res;
    }
};
```

### 解法分析
+ time complexity: O(nlgn)


### 執行結果
![image](https://hackmd.io/_uploads/S1XoFCqaT.jpg)