N бүхэл тоон массив дахь бүх хосуудын нийлбэр f (a [i], a [j])


Хэцүү байдлын түвшин Easy
Байнга асуудаг Cisco Facebook-ийн явган аялал Publicis Sapient
Array Хаш Математик

Асуудлын шийдэл нь n бүхэл тоон массив дахь бүх хосуудын f (a [i], a [j]) - ийн нийлбэрийг 1 <= i <j <= n байхаар бид өгсөн гэж үзэн олохыг хүснэ. массив бүхэл тоонууд.

N бүхэл тоон массив дахь бүх хосуудын нийлбэр f (a [i], a [j])

Жишээ нь

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

Тайлбар

Зөвхөн 3,1 ба 3,1 хосыг хослуулаарай.

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

Тайлбар

Энд бас (1, 3) хоёр хос байна.

Алгоритм

  1. Мэдүүлэх a газрын зураг мөн тохируулах Гаралт 0 ба checksum 0 рүү.
  2. Массивыг дайран өнгөрч би = 0 to i = n,
    1. Гаралт + = (i * a [i]) - хяналтын дүн ба хяналтын дүн + = a [i];
    2. Газрын зураг дээр [i] -1 байгаа эсэхийг шалгана уу.
      1. Хэрэв үнэн бол газрын зургийн [i] -1 утгыг гаралт руу нэмж гаралтыг шинэчлээрэй.
      2. [I] +1 нь газрын зураг дээр түлхүүр болж байгаа эсэхийг шалгана уу. Хэрэв үнэн бол газрын зургийн [i] +1 утгыг гаралт руу нэмж гаралтыг шинэчилнэ үү.
    3. Хэрэв нөхцөл байдлын аль нь ч хангаагүй бол массивын элементийн давтамжийг тоолж, газрын зураг дээр хадгална уу.
  3. Гаралтыг буцаах.

Тайлбар

Бид авсан массив бүхэл тоо, бидний үүрэг бол дээрх нөхцлийг хангасан массивт байгаа бүх хосуудын нийлбэрийг олох явдал юм. Хэрэв хосуудын аль нь ч өгөгдсөн нөхцлийг хангаагүй бол бид зүгээр л буцаана. Үүнийг шийдэхийн тулд a-г ашиглана газрын зураг массивын элемент тус бүр дээр бүх үйлдлүүдийг нэгэн зэрэг хийж, гаралтыг шинэчилж, газрын зураг дээр шалгана. Бид өөрсдийн бодит гарцыг хянадаг нэмэлт хувьсагч авах гэж байгаа бөгөөд үүнийг хяналтын дүн гэж нэрлэж болно. Бид гаралт ба хяналтын нийлбэрийг 0 гэж тохируулна. Ингэснээр бид n бүхэл тоон массив дахь бүх хосуудын нийлбэр f (a [i], a [j]) -г олох болно.

Нэг жишээг авч үзье.

Жишээ нь

Arr [] = {1, 2, 3, 1, 3}, Гаралт: 0, Хяналтын дүн: 0

  • Бид 0-р индексийн элементийг сонгоод дараа нь индексээр үржүүлж, хяналтын дүнг хасаад үр дүнд нь нэмж оруулна.

Гаралт: 0, хяналтын дүн: 1

газрын зураг {1 = 1}, ямар ч нөхцөл хангаж чадахгүй тул бид газрын зураг дээр утгыг нэмнэ.

  • 1-ийн хувьдst индекс элемент, ижил үйлдлийг хий, гэхдээ энэ удаад энэ нь if if-ийн нөхцлийг хангаж, шинэчлэгдсэн гаралтыг авсны дараа бид авах болно.

Шинэчилсэн гаралт: 0, хяналтын дүн: 3

газрын зураг {1 = 1, 2 = 1}, энэ удаад бид энэ утгыг газрын зураг дээр нэмнэ.

  • 2-ийн хувьдnd элемент, өмнөхтэй адил үйлдлийг хийсэн бөгөөд энэ удаад 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

код

N бүхэл тоон массив дахь бүх хосуудын f (a [i], a [j]) нийлбэрийг олох C ++ код

#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

N бүхэл тоон массив дахь бүх хосууд дээр f (a [i], a [j]) -н нийлбэрийг олох Java код

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). Тиймээс n бүхэл тоон массив дахь бүх хосуудын f (a [i], a [j]) -ийн нийлбэрийг олох хугацааны нарийн төвөгтэй байдал нь шугаман болж буурна.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. HashMap-д n түлхүүр оруулах шаардлагатай болж байгаа тул орон зайн нарийн төвөгтэй байдал нь шугаман болно.