N бүтүн сандардан турган массивдеги f (a [i], a [j]) суммасы


Кыйынчылык деңгээли жеңил
Көп суралган Cisco Facebook селсаяктоо Publicis Sapient
согуштук тизме таштанды Math

Маселенин коюлушу 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) эки жуп бар.

Algorithm

  1. Декларация a карта жана орнотуу продукция 0 жана сумма 0 үчүн.
  2. Массивди баштап баштаңыз i = 0 үчүн i = n,
    1. Do output + = (i * a [i]) - контролдук сумма жана контролдук сумма + = a [i];
    2. [I] -1 картада ачкыч катары бар экендигин текшериңиз.
      1. Эгер чын болсо, анда чыккан картанын [i] -1 маанисин кошуу менен чыгарууну жаңыртыңыз.
      2. [I] +1 картада ачкыч катары бар экендигин текшериңиз. Эгер чын болсо, анда чыккан картанын [i] +1 маанисин кошуу менен чыгарууну жаңыртыңыз.
    3. Эгер шарттардын бири дагы канааттандырбаса, анда массив элементинин жыштыгын санап, картага сактаңыз.
  3. Чыгууну кайтаруу.

түшүндүрүү

Бизде бар согуштук тизме бүтүн, биздин милдет - жогорудагы шартты канааттандырган массивде көрсөтүлгөн бардык түгөйлөрдүн суммасын табуу. Эгерде жуптардын бири дагы берилген шартты канааттандырбаса, анда биз жөн гана 0 кайтарабыз. Муну чечүү үчүн а карта жана бир эле мезгилде ар бир массив элементтеринде бардык операцияларды жасап, биздин чыгарууну жаңыртып, биздин Картада да текшерип турабыз. Биздин кошумча өндүрүмүбүзгө көз салган кошумча өзгөрмөнү алганы жатабыз, аны сумма деп атасак болот. Жыйынтыкты жана текшерүү суммасын 0 деп коёбуз. Ошентип, бүтүндөй жуптардын ичинен n сандарынан турган f (a [i], a [j]) суммасын табабыз.

Келгиле, бир мисал карап көрөлү:

мисал

Arr [] = {1, 2, 3, 1, 3}, Чыгуу: 0, Салмак сумма: 0

  • Биз 0-индекстин элементин тандап, андан кийин аткарып, андан кийин анын индексине көбөйтүп, текшерүү суммасын чыгарып, андан кийин аны чыгарууга кошобуз, биз алдык

Чыгуу: 0, Салмак суммасы: 1

карта {1 = 1}, эч кандай шарт канааттандырбайт, андыктан биз анын маанисин картага кошобуз.

  • Анткени 1st индекс элементи, ошол эле операцияны жасаңыз, бирок бул ирет if if операторунун шарттарын канааттандырат жана жаңыланган чыгарылышты алгандан кийин биз алабыз.

Жаңыртылган Чыгуу: 0, Салмак суммасы: 3

карта {1 = 1, 2 = 1}, бул жолу дагы ошол маанини картага пайда болушу менен кошобуз.

  • Анткени 2nd элемент, мурдагыдай эле жасалган иш, бул жолу ал [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 баскычын киргизишибиз керек болгондуктан, мейкиндиктин татаалдыгы сызыктуу болот.