مجموع f (a [i] ، a [j]) على كل الأزواج في مصفوفة من n أعداد صحيحة


مستوى الصعوبة سهل
كثيرا ما يطلب في سيسكو Facebook رفع Publicis Sapient
مجموعة مزيج الرياضيات

تطلب بيان المشكلة معرفة مجموع f (a [i] ، a [j]) على جميع الأزواج في مصفوفة من n أعداد صحيحة بطريقة تجعل 1 <= i <j <= n مع الأخذ في الاعتبار أننا نقدم مجموعة من الأعداد الصحيحة.

مجموع f (a [i] ، a [j]) على كل الأزواج في مصفوفة من n أعداد صحيحة

مثال

arr[] = {1, 2, 3, 1, 3}
4

تفسير

فقط أزواج 3,1،3,1 و XNUMX،XNUMX.

arr[]={2, 2, 1, 1, 3}
4

تفسير

هنا أيضًا ، يوجد زوجان من (1 ، 3).

خوارزمية

  1. تعلن أ رسم خريطة وتعيين الناتج إلى 0 و اختباري ل0.
  2. اجتياز المصفوفة بدءًا من ط = 0 إلى أنا = ن,
    1. هل الإخراج + = (i * a [i]) - المجموع الاختباري والمجموع الاختباري + = a [i] ؛
    2. تحقق مما إذا كان [i] -1 موجودًا كمفتاح في الخريطة.
      1. إذا كان هذا صحيحًا ، فقم بتحديث الإخراج بإضافة قيمة [i] -1 للخريطة في الإخراج.
      2. تحقق مما إذا كان [i] +1 موجودًا كمفتاح في الخريطة. إذا كان هذا صحيحًا ، فقم بتحديث الإخراج بإضافة قيمة [i] +1 للخريطة في الإخراج.
    3. إذا لم يرض أي من الشرط ، فقم ببساطة بحساب وتخزين تكرار عنصر المصفوفة في الخريطة.
  3. عودة الإخراج.

تفسير

حصلنا على مجموعة عدد صحيح، مهمتنا هي معرفة مجموع كل الأزواج الموجودة في مصفوفة تفي بالشرط أعلاه. في حالة عدم استيفاء أي من الأزواج للشرط المحدد ، سنعود ببساطة 0. لحل هذه المشكلة سنستخدم a الخريطة والقيام في نفس الوقت بجميع العمليات على كل عنصر من عناصر المصفوفة وتحديث مخرجاتنا والتحقق من خريطتنا أيضًا. سنأخذ متغيرًا إضافيًا يراقب ناتجنا الحقيقي ، ويمكننا تسميته كمجموع اختباري. سنضبط الناتج والمجمع الاختباري على 0. وهكذا نجد مجموع f (a [i] ، a [j]) على كل الأزواج في مصفوفة من n أعداد صحيحة.

دعنا نأخذ مثالا:

مثال

Arr [] = {1، 2، 3، 1، 3}، الإخراج: 0، المجموع الاختباري: 0

  • سنختار عنصر الفهرس 0 ثم ننفذ ثم نضرب في فهرسه ، ونطرح المجموع الاختباري ثم نضيف ذلك إلى الناتج ، لقد حصلنا على

الإخراج: 0 ، المجموع الاختباري: 1

الخريطة {1 = 1} ، أي شرط لا يُرضي ، لذلك نضيف القيمة إلى الخريطة.

  • ل1st عنصر الفهرس ، قم بنفس العملية ، ولكن هذه المرة ، سوف تفي بشرط أول عبارة if ، وبعد الحصول على الإخراج المحدث ، نحصل على.

الإخراج المحدث: 0 ، المجموع الاختباري: 3

الخريطة {1 = 1 ، 2 = 1} ، هذه المرة أيضًا نضيف هذه القيمة مع حدوثها في الخريطة.

  • ل2nd ، نفس العملية التي تم القيام بها من قبل ، وهذه المرة يجد العنصر a [i] -1 وحصلنا على إخراج محدث:

الإخراج المحدث: 2 ، المجموع الاختباري: 6

الخريطة {1 = 1 ، 2 = 1 ، 3 = 1} ، إضافة العنصر وتردده.

  • بالنسبة للعنصر الثالث ، فإنه يفي بعبارة if الثانية ، مما يعني أنه يتبع إذا كانت الخريطة تحتوي على القيمة a [i] +3 ، ثم بعد حصولنا على الإخراج المحدث:

الإخراج المحدث: 0 ، المجموع الاختباري: 7 ، الخريطة: {1 = 2 ، 2 = 1 ، 3 = 1}

  • للعنصر الرابع ، بعد تمرير أول عبارة if.

الإخراج المحدث: 4 ، المجموع الاختباري: 10

الخريطة {1 = 2 ، 2 = 1 ، 3 = 2}

وسنقوم بإرجاع الناتج: 4

رمز

كود C ++ للعثور على مجموع f (a [i] ، a [j]) على جميع الأزواج في مصفوفة من n أعداد صحيحة

#include<iostream>
#include<unordered_map>

using namespace std;

int sum(int a[], int n)
{
    unordered_map<int, int> count;

    int output = 0, checksum = 0;
    for (int i = 0; i < n; i++)
    {
        output += (i * a[i]) - checksum;
        checksum += a[i];

        if (count[a[i] - 1])
            output -= count[a[i] - 1];

        if (count[a[i] + 1])
            output += count[a[i] + 1];

        count[a[i]]++;
    }
    return output;
}
int main()
{
    int a[] = { 1, 2, 3, 1, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << sum(a, n);
    return 0;
}
4

كود Java للعثور على مجموع f (a [i] ، a [j]) على كل الأزواج في مصفوفة من n أعداد صحيحة

import java.util.HashMap;
public class pairSum
{
    public static int sum(int a[], int n)
    {
        HashMap<Integer,Integer> count = new HashMap<Integer,Integer>();

        int output = 0, checksum = 0;
        for (int i = 0; i < n; i++)
        {
            output += (i * a[i]) - checksum;
            checksum += a[i];

            if (count.containsKey(a[i] - 1))
                output -= count.get(a[i] - 1);

            if (count.containsKey(a[i] + 1))
                output += count.get(a[i] + 1);

            if(count.containsKey(a[i]))
            {
                count.put(a[i], count.get(a[i]) + 1);
            }
            else
            {
                count.put(a[i], 1);
            }
        }
        return output;
    }
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3, 1, 3 };
        int n = a.length;
        System.out.println(sum(a, n));
    }
}
4

تحليل التعقيد

تعقيد الوقت

O (ن) أين "ن" هو عدد العناصر في المصفوفة. يتيح لنا استخدام HashMap إجراء البحث / الحذف / الإدراج بتنسيق يا (1). وهكذا فإن التعقيد الزمني لإيجاد مجموع f (a [i] ، a [j]) على جميع الأزواج في مصفوفة من n أعداد صحيحة ينخفض ​​إلى خطي.

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. نظرًا لأنه قد يتعين علينا إدخال مفاتيح n في HashMap ، فإن تعقيد المساحة يكون خطيًا.