סכום f (a [i], a [j]) על פני כל הזוגות במערך של n מספרים שלמים  


רמת קושי קַל
נשאל לעתים קרובות סיסקו פייסבוק טיול פובליסיס סאפיינט
מערך בליל מתמטיקה

הצהרת הבעיה מבקשת לברר את סכום 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 זוגות בלבד.

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

הסבר

גם כאן, שני זוגות של (1, 3) נמצאים שם.

אַלגוֹרִיתְם  

  1. הכריז א מַפָּה וקבע את תפוקה ל- 0 ו- בדיקת אל 0.
  2. חצו את המערך החל מ i = 0 ל אני = n,
    1. האם פלט + = (i * a [i]) - סכום בדיקה ובדיקת + = a [i];
    2. בדוק אם [i] -1 קיים כמפתח במפה.
      1. אם נכון, עדכן את הפלט על ידי הוספת הערך של [i] -1 של המפה לפלט.
      2. בדוק אם [i] +1 קיים כמפתח במפה. אם נכון, עדכן את הפלט על ידי הוספת הערך של [i] +1 של המפה לפלט.
    3. אם אף אחד מהתנאים לא מקיים, פשוט ספור ואחסן את תדירות אלמנט המערך במפה.
  3. תפוקת החזר.

הסבר

יש לנו מערך מספר שלם, המשימה שלנו היא לגלות את סכום כל הזוגות הקיימים במערך העונה על התנאי הנ"ל. אם אף אחד מהזוגות לא מספק את התנאי הנתון אז פשוט נחזיר 0. כדי לפתור את זה נשתמש ב- מַפָּה ובמקביל לבצע את כל הפעולות בכל אלמנט מערך ולעדכן את התפוקה שלנו ולבדוק גם במפה שלנו. אנו הולכים לקחת משתנה נוסף השומר על התוצר האמיתי שלנו, אנו יכולים לקרוא לו כסך בדיקה. נגדיר את הפלט ואת בדיקת הבדיקה ל- 0. וכך אנו מוצאים את סכום f (a [i], a [j]) על כל הזוגות במערך של n מספרים שלמים.

ראה גם
האלמנט הכי קטן חזר על עצמו בדיוק K Times

הבה נבחן דוגמה:

דוגמה

Arr [] = {1, 2, 3, 1, 3}, פלט: 0, סכום בדיקה: 0

  • נבחר רכיב אינדקס 0 ואז נבצע ואז נכפיל באינדקס שלו, ונחסיר את סכום הבדיקה ואז נוסיף את זה לפלט, קיבלנו

פלט: 0, סכום בדיקה: 1

מפה {1 = 1}, כל תנאי אינו עומד, ולכן אנו מוסיפים את הערך למפה.

  • ל1st אלמנט אינדקס, בצע את אותה פעולה, אך הפעם, זה יספק את תנאי ההצהרה הראשונה אם, ולאחר קבלת הפלט המעודכן, נקבל.

פלט מעודכן: 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 (n) איפה "N" הוא מספר האלמנטים במערך. השימוש ב- HashMap מאפשר לנו לבצע חיפוש / מחיקה / הכנסה פנימה O (1). לפיכך מורכבות הזמן למציאת סכום f (a [i], a [j]) על פני כל הזוגות במערך של n מספרים שלמים מצטמצמת לליניארית.

ראה גם
תבנית מילים

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך. מכיוון שאולי נצטרך להכניס n מקשים ל- HashMap, לכן מורכבות החלל היא ליניארית.