ການຊ້ອນກັນຂອງສອງ Arrays II Leetcode Solution  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ເຟສບຸກ ກູໂກ Oracle
ຂັ້ນຕອນວິທີ ລະຫັດ HashMap ການສໍາພາດ ການສໍາພາດກ່ອນ LeetCode LeetCodeSolutions ຮຽງລໍາດັບ ສອງຈຸດ

ຖະແຫຼງການບັນຫາ  

ໃນບັນຫານີ້ສອງຢ່າງ ອາຄານ ໄດ້ຖືກມອບໃຫ້ແລະພວກເຮົາຕ້ອງຊອກຮູ້ຈຸດຕັດກັນຂອງສອງອາຄານນີ້ແລະສົ່ງຄືນຜົນທີ່ໄດ້ຮັບ.
ແຕ່ລະອົງປະກອບທີ່ຢູ່ໃນຜົນໄດ້ຮັບຄວນປາກົດເປັນຫຼາຍເທື່ອຕາມທີ່ມັນສະແດງຢູ່ໃນທັງສອງຂບວນ. ຜົນໄດ້ຮັບສາມາດຢູ່ໃນຄໍາສັ່ງໃດໆ.

ຍົກຕົວຢ່າງ

nums1 = [1,2,2,1], nums2 = [2,2]
[2,2]
nums1 = [4,9,5], nums2 = [9,4,9,8,4]
[4,9]

ວິທີການ 1 (ການ ນຳ ໃຊ້ ແຜນທີ່ Hash 

ເພື່ອຊອກຫາຈຸດຕັດກັນຂອງສອງອາຄານ (ເລກ 1 ແລະ ເລກ 2) ພວກເຮົາ ທຳ ອິດສາມາດເກັບຄ່ານັບຂອງແຕ່ລະອົງປະກອບຂອງ ໜຶ່ງ ແຖວ (ໃຫ້ ເລກ 1) ໂດຍໃຊ້ແຜນທີ່ Hash. ຫຼັງຈາກນັ້ນພວກເຮົາສາມາດຂ້າມຜ່ານແຖວທີສອງ (ເລກ 2) ແລະ ສຳ ລັບແຕ່ລະອົງປະກອບໃນ num2 ພວກເຮົາຈະກວດເບິ່ງວ່ານັບຂອງອົງປະກອບນັ້ນຢູ່ໃນ num1 ແມ່ນບວກຫລືບໍ່.

  • ຖ້ານັບ nums2 [i] ໃນ array nums1 ແມ່ນບວກ, ຫຼັງຈາກນັ້ນຕື່ມອົງປະກອບນີ້ (nums2 [i]) ໃນຂບວນຜົນ. ແລະຫຼຸດລົງການນັບອົງປະກອບນີ້ໃນແຜນທີ່ Hash.
  • ອີກປະການ ໜຶ່ງ ສ່ວນປະກອບນີ້ຈະບໍ່ຖືກຕື່ມເຂົ້າໃນຜົນ.

ໝາຍ ເຫດ: ພວກເຮົາຈະເກັບສ່ວນປະກອບຂອງແຖວນັ້ນໄວ້ໃນແຜນທີ່ທີ່ມີຂະ ໜາດ ນ້ອຍກວ່າເພື່ອເຮັດໃຫ້ພື້ນທີ່ມີຄວາມສັບສົນ ໜ້ອຍ ທີ່ສຸດ.

ເບິ່ງ
Leetcode Pascal

ການຈັດຕັ້ງປະຕິບັດ ສຳ ລັບການຊ້ອນກັນຂອງສອງ Arrays II Leetcode Solution

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

    if(nums1.size()>nums2.size()){
        swap(nums1,nums2);
    }

    unordered_map< int , int >  m;
    for(auto val:nums1){
        m[val]++;
    }

    int k=0;
    for(auto val:nums2){
        if(m[val]>0){
            nums1[k++]=val;
            --m[val];
        }
    }

    return vector<int>(nums1.begin(),nums1.begin()+k);

}

int main() 
{
    vector<int> nums1={1,2,2,1};
    vector<int> nums2={2,2};
    vector<int> ans=intersect(nums1,nums2);
    for(int x:ans)
        cout<<x<<" ";
   return 0; 
}
[2,2]

ໂຄງການ Java

import java.util.*;
class Rextester{
    
    public static int[] intersect(int[] nums1, int[] nums2)
    {
        if(nums1.length>nums2.length){
            return intersect(nums2,nums1);
        }

        Map<Integer,Integer>  m= new HashMap<Integer,Integer>();
        for(int val:nums1){
            m.put(val,m.getOrDefault(val,0)+1);
        }

        int k=0;
        for(int val:nums2){
            if(m.getOrDefault(val,0)>0){
                nums1[k++]=val;
                m.put(val,m.get(val)-1);
            }
        }

        int ans[]=new int[k];
        for(int i=0;i<k;i++){
            ans[i]=nums1[i];
        }

        return ans;
    }
    
  public static void main(String args[])
    {
        int[] nums1={1,2,2,1};
        int[] nums2={2,2};
    int[] ans=intersect(nums1,nums2);
        for(int x:ans)
            System.out.print(x+" ");
    }
}
[2,2]

ການວິເຄາະທີ່ຊັບຊ້ອນ ສຳ ລັບການເຈາະຂອງສອງ Arrays II Leetcode Solution

ຄວາມສັບສົນເວລາ

O (n + m): ບ່ອນທີ່ n ແລະ m ແມ່ນຄວາມຍາວຂອງຂບວນ. ພວກເຮົາປ່ຽນເສັ້ນທາງເສັ້ນຜ່ານທັງອາຄານແລະການປະຕິບັດງານແລະການດຶງເອົາແລະເຮັດແຜນທີ່ໃນແຜນທີ່ຕ້ອງໃຊ້ເວລາຄົງທີ່.

ຄວາມສັບສົນໃນອະວະກາດ 

O (min (n, ມ)): ພວກເຮົານໍາໃຊ້ແຜນທີ່ hash ເພື່ອເກັບຮັກສາອົງປະກອບຂອງຂບວນນ້ອຍກວ່າ.

ວິທີທີ່ 2 (ໃຊ້ສອງຈຸດ)  

ຖ້າອົງປະກອບຂອງທັງສອງຂບວນຖືກຈັດຮຽງແລ້ວວິທີການນີ້ຈະມີປະສິດຕິພາບຫຼາຍຂື້ນ. ສຳ ລັບບັນຫານີ້ຍ້ອນວ່າມັນບໍ່ຖືກຈັດຮຽງພວກເຮົາ ການຈັດລຽງ ທັງອາຄານທັງ ໝົດ ກ່ອນ.
ຕອນນີ້ພວກເຮົາຈະ ນຳ ໃຊ້ສອງ point i ແລະ j ສຳ ລັບສອງແຖວແລະເລີ່ມຕົ້ນທັງສອງດ້ວຍເລກສູນ.
ຍ້າຍດັດຊະນີ i ຕາມແຖວທີ 1 (ເລກ 1) ແລະດັດສະນີ j ຕາມແຖວທີ 2 (ເລກ 2)

  • ປຽບທຽບສອງອົງປະກອບທີ່ຊີ້ໂດຍ i ແລະ j.
  • If nums1 [i] ແມ່ນຫນ້ອຍກ່ວາ nums2 [ຈ. ຫຼັງຈາກນັ້ນພວກເຮົາຮູ້ວ່າພວກເຮົາຕ້ອງອອກຈາກອົງປະກອບນ້ອຍກວ່າແລະໄປຫາອົງປະກອບທີ່ໃຫຍ່ກວ່າ (ເກົ່າ) ໃນ nums1 array ເພື່ອກວດສອບການແຍກຂອງອົງປະກອບ.
  • ອື່ນຖ້າ nums1 [i] ແມ່ນຫຼາຍກ່ວາ nums2 [ຈ. ຫຼັງຈາກນັ້ນຄ້າຍຄືກັນພວກເຮົາຕ້ອງໄປຕໍ່ (ຕໍ່ໄປ) ອົງປະກອບໃນ nums2 array.
  • ອື່ນທັງສອງອົງປະກອບຕັດກັນ, ເພາະສະນັ້ນຈຶ່ງເພີ່ມອົງປະກອບນີ້ໃຫ້ກັບຜົນໄດ້ຮັບ. ແລະການເພີ່ມຂື້ນທັງ i ແລະ j.
ເບິ່ງ
ການແລກປ່ຽນຂັ້ນຕ່ ຳ ເພື່ອເຮັດໃຫ້ການແກ້ໄຂບັນຫາແບບ Leetcode ເທົ່າທຽມກັນ

ສາມາດເຮັດໃຫ້ເຫັນພາບໂດຍໃຊ້ຕົວຢ່າງໃນຮູບຂ້າງລຸ່ມນີ້:

ການຊ້ອນກັນຂອງສອງ Arrays II Leetcode Solution

 

ການຈັດຕັ້ງປະຕິບັດ ສຳ ລັບການຊ້ອນກັນຂອງສອງ Arrays II Leetcode Solution

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) 
{
    sort(nums1.begin(),nums1.end());
    sort(nums2.begin(),nums2.end());

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

    return vector<int>(nums1.begin(),nums1.begin()+k);
}

int main() 
{
    vector<int> nums1={1,2,2,1};
    vector<int> nums2={2,2};
    vector<int> ans=intersect(nums1,nums2);
    for(int x:ans)
        cout<<x<<" ";
   return 0; 
}
[2,2]

ໂຄງການ Java

import java.util.*;
class Rextester{
    
    public static int[] intersect(int[] nums1, int[] nums2)
    {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i=0,j=0,k=0;
        while(i<nums1.length && j<nums2.length)
        {
            if(nums1[i]<nums2[j]) i++;
            else if(nums1[i]>nums2[j]) j++;
            else{
                nums1[k++]=nums1[i];
                ++i;++j;
            }
        }
        
        int ans[]=new int[k];
        for(i=0;i<k;i++){
            ans[i]=nums1[i];
        }

        return ans;    
    }
    
  public static void main(String args[])
    {
        int[] nums1={1,2,2,1};
        int[] nums2={2,2};
    int[] ans=intersect(nums1,nums2);
        for(int x:ans)
            System.out.print(x+" ");
    }
}
[2,2]

ການວິເຄາະທີ່ຊັບຊ້ອນ ສຳ ລັບການເຈາະຂອງສອງ Arrays II Leetcode Solution

ຄວາມສັບສົນເວລາ

O (logn + logm): ພວກເຮົາຈັດຮຽງທັງສອງແຖວທີ່ມີຂະ ໜາດ n ແລະ m. ແລະຫຼັງຈາກນັ້ນພວກເຮົາ iterate linearly ກ່ຽວກັບອາຄານທັງສອງ.

ຄວາມສັບສົນໃນອະວະກາດ 

O (ສູງສຸດ (logn, logm)) ເຖິງ O (max (n, m)): ມັນຂື້ນກັບການຮຽງລໍາດັບສູດທີ່ພວກເຮົາເຄີຍໃຊ້.