8ms accepted C++ code with efficiency O(n)


  • 0
    C
        int mymin(int a, int b){
            if (a<b) return a;
            return b;
        }
        
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            if(nums1.empty()) return nums1;
            else if (nums2.empty()) return nums2;
            
            vector <int> newarr;
            
            int len1 = nums1.size();
            int len2 = nums2.size();
            int largest1 = nums1[0];
            int largest2 = nums2[0];
            
            for(int i = 0; i < len1; ++i){// find the largest number
                if(largest1 < nums1[i]){
                    largest1 = nums1[i];
                }
            }
            for(int i = 0; i < len2; ++i){// find the largest number
                if(largest2 < nums2[i]){
                    largest2 = nums2[i];
                }
            }
            
            int track1[largest1+1] = {0};
            int track2[largest2+1] = {0};
          
            for(int i = 0; i < len1; ++i){
                ++track1[nums1[i]];
            }
            for(int i = 0; i < len2; ++i){
                ++track2[nums2[i]];
            }
            
            if(largest1 < largest2){
                for(int i = 0; i <= largest1; ++i){
                    if(track1[i] >= 1 && track2[i] >= 1){
                        for(int j = 0; j < min(track1[i], track2[i]); ++j){
                            newarr.push_back(i);
                        }
                    }
                }
            } else {
                for(int i = 0; i <= largest2; ++i){
                    if(track1[i] >= 1 && track2[i] >= 1){
                        for(int j = 0; j < min(track1[i], track2[i]); ++j){
                            newarr.push_back(i);
                        }
                    }
                }
            }
            return newarr;
        }

  • 1

    Consider if I have

    nums1[] = {12,2147483647}
    nums2[] = {12,21}

    Now, track1's length will be 2147483648.

    So surely, we would be out of heap memory. Isn't it ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.