تقاطع حل صفيفين II Leetcode


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون فيسبوك جوجل أوراكل
خريطة التجزئة فرز اثنين من المؤشرات

المشكلة بيان

في هذه المشكلة الثانية المصفوفات معطاة وعلينا معرفة تقاطع هاتين المصفوفتين وإرجاع المصفوفة الناتجة.
يجب أن يظهر كل عنصر في النتيجة عدة مرات كما يظهر في كلا المصفوفتين. يمكن أن تكون النتيجة بأي ترتيب.

مثال

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

المقاربة 1 (استخدام خريطة التجزئة)

لمعرفة تقاطع صفيفتين (الأعداد 1 و الأعداد 2) يمكننا أولاً تخزين عدد كل عنصر في مجموعة واحدة (let الأعداد 1) باستخدام خريطة التجزئة. ثم يمكننا اجتياز المصفوفة الثانية (الأعداد 2) ولكل عنصر في nums2 نتحقق مما إذا كان عدد هذا العنصر في nums1 موجبًا أم لا.

  • إذا كان العد nums2 [i] في المصفوفات 1 تكون موجبة ، ثم أضف هذا العنصر (nums2 [i]) في مصفوفة النتائج. وتقليل عدد هذا العنصر في خريطة التجزئة.
  • وإلا فلن يتم إضافة هذا العنصر في النتيجة.

ملاحظة: سنقوم بتخزين عناصر هذه المصفوفة في خريطة التجزئة التي يكون حجمها أصغر لتقليل تعقيد المساحة.

تنفيذ تقاطع حل صفيفين II Leetcode

برنامج 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]

برنامج جافا

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]

تحليل التعقيد لتقاطع حل صفيفين II Leetcode

تعقيد الوقت

س (ن + م): حيث n و m أطوال الصفيف. نحن نكرر خطيًا من خلال كل من المصفوفات ، وتستغرق عملية الإدراج والجلب في خريطة التجزئة وقتًا ثابتًا.

تعقيد الفضاء 

O (دقيقة (ن ، م)): نستخدم خريطة التجزئة لتخزين عناصر المصفوفة الأصغر.

النهج 2 (استخدام مؤشرين)

إذا تم فرز عناصر كل من المصفوفة ، فإن هذا الأسلوب يكون أكثر كفاءة. لهذه المشكلة كما لم يتم فرزها نحن sort كلا المصفوفتين أولاً.
سنستخدم الآن مؤشرين i و j للمصفوفتين ونبدأ كلاهما بصفر.
حرك الفهرس i على طول الصفيف الأول (الأعداد 1) وفهرسة j على طول الصفيف الثاني (الأعداد 2)

  • قارن بين العنصرين المشار إليهما بـ i و j.
  • If nums1 [i] أقل من أرقام 2 [ي] ثم نعلم أنه يتعين علينا ترك العنصر الأصغر والانتقال إلى العنصر التالي (الأكبر) في المصفوفة nums1 للتحقق من تقاطع العناصر.
  • إذا كان آخر nums1 [i] أكبر من أرقام 2 [ي] ثم بالمثل يجب علينا الانتقال إلى العنصر التالي (الأكبر) في مجموعة nums2.
  • عدا ذلك ، تقاطع كلا العنصرين ، وبالتالي أضف هذا العنصر إلى مصفوفة النتائج. وتزيد كل من i و j.

دعنا نتخيل باستخدام مثال في الشكل أدناه:

تقاطع حل صفيفين II Leetcode

 

تنفيذ تقاطع حل صفيفين II Leetcode

برنامج 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]

برنامج جافا

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]

تحليل التعقيد لتقاطع حل صفيفين II Leetcode

تعقيد الوقت

O (تسجيل الدخول + سجل م): نقوم بفرز كلا المصفوفتين اللتين حجمهما n و m. ثم نقوم بالتكرار خطيًا على كلا المصفوفتين.

تعقيد الفضاء 

O (حد أقصى (تسجيل دخول ، سجل م)) إلى O (حد أقصى (ن ، م)): يعتمد ذلك على خوارزمية الفرز التي استخدمناها.