عد الأزواج بالمجموع المعطى


مستوى الصعوبة سهل
كثيرا ما يطلب في Accolite أمازون مجموعة الحقائق رفع
مجموعة مزيج الرياضيات فرز

إعطاء عدد صحيح مجموعة بالحجم n ، والعدد الصحيح "K" ، تحتاج إلى حساب عدد الأزواج (لا يلزم أن تكون فريدة) الموجودة في المصفوفة التي يساوي مجموعها "K".

مثال

الإدخال:

وصول = {1، 5، 7، 1}

K = 6

الإخراج:

2

حل القوة الغاشمة لأزواج العد بالمجموع المعطى

الفكرة الرئيسية

يمكننا التكرار على جميع أزواج المصفوفة المحددة ، ثم عد الأزواج التي يساوي مجموعها K.

خوارزمية

  1. تهيئة إجابة متغيرة = 0.
  2. قم بتشغيل حلقة لـ I في النطاق من 0 إلى n-1
    1. قم بتشغيل حلقة لـ j في النطاق i + 1 إلى n-1 ؛
      1. إذا كانت arr [i] + arr [j] تساوي k ، فإن زيادة الإجابة بمقدار 1.
  3. عودة الجواب.

تطبيق

برنامج C ++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]+a[j]==k){
                ans++;
            }
        }
    }
    cout<<"Number of pairs with the given sum are: "<<ans;
}
4 6
1  5  7 1
Number of pairs with the given sum are: 2

برنامج جافا

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]+a[j]==k){
                    ans++;
                }
            }
        }
    System.out.println("Number of pairs with the given sum are: "+ans);
  }
}

6 4
2 2 3 1 1 5
Number of pairs with the given sum are: 3

تحليل التعقيد لأزواج العد بالمجموع المعطى

تعقيد الوقت

نظرًا لأننا نكرر جميع الأزواج وهناك ما يقرب من أزواج N ^ 2 ، فإن التعقيد الزمني الإجمالي هو O (N ^ 2).

تعقيد الفضاء

لم نستخدم أي مساحة إضافية ، لذا فإن تعقيد الفضاء هو O (1).

مفهوم التجزئة لأزواج العد بالمجموع المعطى

الفكرة الرئيسية

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

الآن سوف نكرر المصفوفة ونضيف كل العناصر التي تساوي قيمتها k-arr [i].

لكن علينا التحقق من شرط واحد:

إذا كانت arr [i] تساوي k-arr [i] ، فسنطرح 1 من إجابتنا لأنه يتعين علينا إيجاد أزواج مميزة ، لذلك لا يمكننا أخذ arr [i] مرتين للزوج ، ولهذا السبب سنطرح هذا حالة من إجابتنا.

خوارزمية

  1. قم بعمل جدول تجزئة يخزن عدد كل عنصر في المصفوفة.
  2. كرر المصفوفة لـ I في النطاق من 0 إلى n-1
    1. إذا كانت arr [i] تساوي k-arr [i] ، أضف (count_of (k-arr [i]) - 1) للإجابة.
    2. إذا كانت arr [i] لا تساوي k-arr [i] ، فقم بإضافة (count_of (k-arr [i]) للإجابة.
  3. عودة الجواب.

مثال

جدول التجزئة الذي تم إنشاؤه للمصفوفة = {1، 2، 3، 3، 4، 1، 1} هو:

عد الأزواج بالمجموع المعطى

تطبيق

برنامج C ++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> fre;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        fre[arr[i]]++;
    }
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == k - arr[i])
        {
            answer += (fre[arr[i]] - 1);
        }
        else
        {
            answer += (fre[k - arr[i]]);
        }
    }
    answer /= 2;
    cout << "Number of pairs with the given sum are: "<<answer << endl;
    return 0;
}
6 4
1 2 2 2 3 4
Number of pairs with the given sum are: 4

برنامج جافا

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        HashMap<Integer, Integer> fre = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            Integer j = fre.get(arr[i]); 
            fre.put(arr[i], (j == null) ? 1 : j + 1); 
        }
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == k - arr[i])
            {
                answer += (fre.get(arr[i]) - 1);
            }
            else
            {
                Integer j = fre.get(k - arr[i]); 
                if(j!=null)
                    answer += j;
            }
        }
        answer /= 2;
    System.out.println("Number of pairs with the given sum are: "+answer);
  }
}

6 7
3 5 6 1 4 4
Number of pairs with the given sum are: 3

تحليل التعقيد لأزواج العد بالمجموع المعطى

تعقيد الوقت

نحن نكرر المصفوفة مرة واحدة فقط ، لذا فإن التعقيد الزمني هو O (N).

تعقيد الفضاء

نحن نحتفظ بجدول تجزئة ، لذا فإن تعقيد مساحتنا هو O (N).

المراجع