مجموع f (a [i] ، a [j]) بیش از همه جفت ها در یک آرایه از n عدد صحیح


سطح دشواری ساده
اغلب در سیسکو فیس بوک پیاده روی 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 به من = n,
    1. خروجی را انجام دهید = = (i * a [i]) - جمع کنترلی و جمع کنترلی + = a [i] ؛
    2. بررسی کنید که آیا [i] -1 به عنوان کلید در نقشه وجود دارد یا خیر.
      1. اگر درست است ، پس با افزودن مقدار [i] -1 نقشه به خروجی ، خروجی را به روز کنید.
      2. بررسی کنید که آیا [1] +1 به عنوان یک کلید در نقشه وجود دارد یا خیر. اگر درست است ، سپس با افزودن مقدار XNUMX+ [i] نقشه به خروجی ، خروجی را به روز کنید.
    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 عنصر index ، همان عملیات را انجام می دهیم ، اما این بار ، شرط اولین دستور if را برآورده می کند ، و پس از دریافت خروجی به روز شده ، ما دریافت می کنیم.

خروجی به روز شده: 0 ، چک کنکور: 3

نقشه {1 = 1 ، 2 = 1} ، این بار نیز آن مقدار را با ظهور آن به نقشه اضافه می کنیم.

  • برای 2nd عنصر ، همان عملیاتی که قبلاً انجام شده است ، این بار عنصر a [i] -1 را پیدا می کند و خروجی به روز شده ای داریم:

خروجی به روز شده: 2 ، چک کنکور: 6

نقشه {1 = 1 ، 2 = 1 ، 3 = 1} ، عنصر و فرکانس آن را جمع کنید.

  • برای عنصر 3 ، دستور if دوم را برآورده می کند ، بدین معنی که اگر نقشه حاوی مقدار a [i] +1 باشد ، پس از آنکه خروجی به روز شده را بدست آوردیم ، دنبال می کند:

خروجی به روز شده: 0 ، جمع کنکور: 7 ، نقشه: {1 = 2 ، 2 = 1 ، 3 = 1}

  • برای عنصر 4 ، پس از گذر از اولین جمله 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

کد جاوا برای یافتن جمع 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 (N) جایی که "n" تعداد عناصر آرایه است. استفاده از HashMap به ما امکان می دهد جستجو / حذف / درج را انجام دهیم O (1). بنابراین پیچیدگی زمانی برای یافتن مجموع f (a [i] ، a [j]) بر روی همه جفت ها در یک آرایه از n عدد صحیح به خطی کاهش می یابد.

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است. از آنجا که ممکن است مجبور باشیم n کلید در HashMap وارد کنیم ، بنابراین پیچیدگی فضا خطی است.