F (a [i], a [j]) ჯამი n მთელი რიცხვის მასივში


Რთული ტური Easy
ხშირად ეკითხებიან Cisco Facebook ლაშქრობა პუბლიკის საპიენტი
Array Hash მათემატიკის

პრობლემის დებულება ითხოვს 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-მდე და ამოწმებს to 0.
  2. მასივის გადაკვეთა დაწყებული i = 0 to მე = ნ,
    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}, დაამატეთ ელემენტს და მის სიხშირეს.

  • მე -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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. HashMap– ის გამოყენება საშუალებას გვაძლევს შევასრულოთ ძიება / წაშლა / ჩასმა O (1). ამრიგად, f (a [i], a [j]) ჯამის მოძიების დროის სირთულე n მთელი რიცხვის მასივში ყველა წყვილზე შემცირებულია ხაზოვანი.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. მას შემდეგ, რაც შეიძლება HashMap- ში n გასაღების ჩასმა მოგიწიოთ, სივრცის სირთულე ხაზოვანია.