LeetCode 여행: 350. 두 배열 의 교 집합 II

제목:
두 개의 배열 을 정 하고 하나의 함 수 를 만들어 서 그들의 교 집합 을 계산 합 니 다.
예시 1:
입력: nums 1 = [1, 2, 2, 1], nums 2 = [2, 2] 출력: [2, 2] 예시 2:
입력: nums 1 = [4, 9, 5], nums 2 = [9, 4, 9, 8, 4] 출력: [4, 9] 설명:
출력 결과 에 있 는 모든 요소 가 나타 나 는 횟수 는 요소 가 두 배열 에 나타 나 는 횟수 와 일치 해 야 합 니 다.우 리 는 출력 결과 의 순 서 를 고려 하지 않 아 도 된다.진급:
주어진 배열 이 정렬 되 어 있다 면?당신 은 어떻게 당신 의 알고리즘 을 최적화 할 것 입 니까?만약 nums 1 의 크기 가 nums 2 보다 훨씬 작다 면 어떤 방법 이 더 좋 습 니까?만약 nums 2 의 요소 가 디스크 에 저장 된다 면 디스크 메모리 가 제한 되 어 있 고 모든 요 소 를 메모리 에 한 번 에 불 러 올 수 없습니다. 어떻게 해 야 합 니까?
해법 1:
먼저 정렬 을 하고 더 블 교체 기 를 이동 합 니 다.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        //     
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        
        vector<int> resVec;
        
        //     
        vector<int>::iterator itNums1 = nums1.begin();
        vector<int>::iterator itNums2 = nums2.begin();
        
        while(itNums1 != nums1.end() && itNums2 != nums2.end()){
            if(*itNums1 < *itNums2)
                ++itNums1;
            else if(*itNums1 > *itNums2)
                ++itNums2;
            else{
                resVec.push_back(*itNums1);
                ++itNums1;
                ++itNums2;
            }
        }
        
        return resVec;
    }
};

C + + 라 이브 러 리 함수 sort, qsort:https://blog.csdn.net/zzzmmmkkk/article/details/4266888
해법 2:
요소 가 나타 나 는 횟수 를 고려 해 야 하기 때문에 map 저장 과 검색 을 사용 합 니 다.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int,int> nums1Map;
        for(int i = 0; i < nums1.size(); i++){
            nums1Map[nums1[i]]++;
        }

        vector<int> resVec;
        for(int i = 0; i < nums2.size(); i++){
            if(nums1Map[nums2[i]] > 0){
                resVec.push_back(nums2[i]);
                nums1Map[nums2[i]]--;
            }                
        }
        return resVec;
    }
};

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> nums1Map;
        for(auto num1 : nums1){
            nums1Map[num1]++;
        }
        
        vector<int> resVec;
        for(auto num2 : nums2){
            if(nums1Map[num2] > 0){
                resVec.push_back(num2);
                nums1Map[num2]--;
            }
        }
        return resVec;
    }
};

해법 3:
배열 에 표지 자릿수 그룹 을 만들다.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        
        vector<int> resVec;
        //      ，  ：              ，
        //                  。
        vector<bool> bl(nums2.size());
        
        for(int i = 0; i < nums1.size(); ++i){
            for(int j = 0; j < nums2.size(); ++j){
                if(nums1[i] == nums2[j] && bl[j] == false){
                    resVec.push_back(nums1[i]);
                    bl[j] = true;
                    break;
                }
            }
        }
        
        return resVec;
    }
};

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        
        vector<int> resVec;
        //      ，  ：              ，
        //                  。
        vector<bool> bl(nums2.size());

        for(auto num1 : nums1){
            int j = 0;
            for(auto num2 : nums2){
                if(num1 == num2 && bl[j] == false){
                    resVec.push_back(num1);
                    bl[j] = true;
                    break;
                }
                ++j;
            }
        }
        
        return resVec;
    }
};

해법 이 가장 좋 고 해법 이 두 번 째 이 며 해법 이 세 번 째 가 가장 느리다.