ผลรวมของ 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 เท่านั้น

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

คำอธิบาย

นอกจากนี้ยังมีสองคู่ (1, 3) อยู่ที่นั่น

ขั้นตอนวิธี

  1. ประกาศก แผนที่ และตั้งค่า เอาท์พุต ถึงปี 0 และ การตรวจสอบ เพื่อ 0
  2. สำรวจอาร์เรย์โดยเริ่มจาก i = 0 ไปยัง ผม = n,
    1. ทำเอาต์พุต + = (i * a [i]) - checksum และ checksum + = 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, Checksum: 0

  • เราจะเลือกองค์ประกอบดัชนีที่ 0 จากนั้นทำการแล้วคูณด้วยดัชนีและลบการตรวจสอบแล้วบวกเข้าไปในผลลัพธ์เราได้

เอาต์พุต: 0, Checksum: 1

แผนที่ {1 = 1} เงื่อนไขใด ๆ ไม่เป็นไปตามนั้นเราจึงเพิ่มมูลค่าลงในแผนที่

  • สำหรับ 1st องค์ประกอบดัชนีทำการดำเนินการเดียวกัน แต่คราวนี้จะเป็นไปตามเงื่อนไขของคำสั่ง if แรกและหลังจากได้รับผลลัพธ์ที่อัปเดตแล้วเราจะได้รับ

อัปเดตเอาต์พุต: 0, Checksum: 3

แผนที่ {1 = 1, 2 = 1} คราวนี้เราก็เพิ่มค่านั้นด้วยการเกิดขึ้นในแผนที่ด้วย

  • สำหรับ 2nd องค์ประกอบการดำเนินการเดียวกันกับก่อนหน้านี้คราวนี้พบองค์ประกอบ a [i] -1 และเราได้รับเอาต์พุตที่อัปเดต:

อัปเดตเอาต์พุต: 2, Checksum: 6

แมป {1 = 1, 2 = 1, 3 = 1} เพิ่มองค์ประกอบและความถี่

  • สำหรับองค์ประกอบที่ 3 เป็นไปตามคำสั่ง if ที่สองซึ่งหมายความว่าตามมาหากแผนที่มีค่า a [i] +1 หลังจากนั้นเราได้รับเอาต์พุตที่อัปเดตแล้ว:

อัปเดตผลลัพธ์: 0, Checksum: 7, แผนที่: {1 = 2, 2 = 1, 3 = 1}

  • สำหรับองค์ประกอบที่ 4 หลังจากผ่านคำสั่ง if แรก

อัปเดตเอาต์พุต: 4, Checksum: 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 ดังนั้นความซับซ้อนของพื้นที่จึงเป็นแบบเส้นตรง