ຜົນບວກຂອງ f (a [i], a [j]) ເໜືອ ທຸກຄູ່ໃນແຖວຂອງຕົວເລກ n


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Cisco ເຟສບຸກ hike Publicis Sapient
Array Hash ຄະນິດສາດ

ຄຳ ຖະແຫຼງທີ່ມີບັນຫາຂໍໃຫ້ຄົ້ນຫາ Sum of 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. ປະກາດກ ແຜນທີ່ ແລະຕັ້ງຄ່າ output ເຖິງ 0 ແລະ Checkum to 0
  2. ລອກລວງອາເລເລີ່ມຈາກ i = 0 to i = ນ,
    1. ເຮັດຜົນໄດ້ຮັບ + = (i * a [i]) - checksum ແລະ checksum + = a [i];
    2. ກວດເບິ່ງວ່າ a [i] -1 ມີປະຈຸບັນເປັນກຸນແຈໃນແຜນທີ່ຫລືບໍ່.
      1. ຖ້າຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນປັບປຸງຜົນຜະລິດໂດຍເພີ່ມມູນຄ່າຂອງ [i] -1 ຂອງແຜນທີ່ເຂົ້າໃນຜົນຜະລິດ.
      2. ກວດເບິ່ງວ່າ a [i] +1 ມີຢູ່ໃນປຸ່ມທີ່ຢູ່ໃນແຜນທີ່ຫລືບໍ່. ຖ້າຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນປັບປຸງຜົນຜະລິດໂດຍການເພີ່ມຄ່າຂອງ [i] +1 ຂອງແຜນທີ່ເຂົ້າໃນຜົນຜະລິດ.
    3. ຖ້າບໍ່ມີເງື່ອນໄຂໃດທີ່ພໍໃຈ, ຫຼັງຈາກນັ້ນພຽງແຕ່ນັບແລະເກັບຄວາມຖີ່ຂອງອົງປະກອບຂບວນເຂົ້າໄປໃນແຜນທີ່.
  3. ກັບຄືນຜົນຜະລິດ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ຮັບ array integer, ວຽກງານຂອງພວກເຮົາແມ່ນເພື່ອຊອກຫາຜົນລວມຂອງຄູ່ທັງ ໝົດ ທີ່ປະກົດຢູ່ໃນຂບວນທີ່ ເໝາະ ສົມກັບເງື່ອນໄຂຂ້າງເທິງ. ຖ້າຫາກວ່າບໍ່ມີຄູ່ໃດຕອບສະ ໜອງ ເງື່ອນໄຂທີ່ໄດ້ ກຳ ນົດໃຫ້ພວກເຮົາກັບຄືນ 0. ເພື່ອແກ້ໄຂບັນຫານີ້ພວກເຮົາຈະ ນຳ ໃຊ້ a ແຜນທີ່ ແລະພ້ອມກັນເຮັດທຸກການ ດຳ ເນີນງານໃນແຕ່ລະອົງປະກອບຂອງອາເລແລະປັບປຸງຜົນຜະລິດຂອງພວກເຮົາແລະກວດເບິ່ງແຜນທີ່ຂອງພວກເຮົາເຊັ່ນກັນ. ພວກເຮົາ ກຳ ລັງຈະເອົາຕົວແປພິເສດທີ່ຮັກສາຕາໃຫ້ຜົນໄດ້ຮັບຕົວຈິງຂອງພວກເຮົາ, ພວກເຮົາສາມາດເອີ້ນມັນວ່າເຊັກ. ພວກເຮົາຈະ ກຳ ນົດຄ່າຜົນຜະລິດແລະເຊັກໄລ່ໃຫ້ 0. ແລະນັ້ນແມ່ນວິທີທີ່ພວກເຮົາຊອກຫາຜົນລວມຂອງ f (a [i], a [j]) ເໜືອ ທຸກຄູ່ໃນແຖວຂອງ ຈຳ ນວນ n.

ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງ:

ຍົກຕົວຢ່າງ

Arr [] = {1, 2, 3, 1, 3}, ຜົນໄດ້ຮັບ: 0, Checksum: 0

  • ພວກເຮົາຈະເລືອກເອົາອົງປະກອບດັດສະນີ 0th ແລະຈາກນັ້ນປະຕິບັດແລະຫຼັງຈາກນັ້ນຄູນດ້ວຍດັດຊະນີຂອງມັນ, ແລະການຫັກລົບເຊັກແລະຈາກນັ້ນເພີ່ມເຂົ້າໃນຜົນຜະລິດ, ພວກເຮົາໄດ້

ຜົນໄດ້ຮັບ: 0, Checksum: 1

ແຜນທີ່ {1 = 1}, ເງື່ອນໄຂໃດກໍ່ຕາມບໍ່ພໍໃຈ, ສະນັ້ນພວກເຮົາຈຶ່ງເພີ່ມຄ່າເຂົ້າໃນແຜນທີ່.

  • ສໍາຫລັບ 1st ອົງປະກອບດັດສະນີ, ເຮັດການປະຕິບັດງານແບບດຽວກັນ, ແຕ່ເວລານີ້, ມັນຈະພໍໃຈກັບສະພາບຂອງການ ທຳ ອິດຖ້າມີການຖະແຫຼງ, ແລະຫລັງຈາກໄດ້ຮັບຜົນຜະລິດທີ່ຖືກປັບປຸງ, ພວກເຮົາໄດ້ຮັບ.

ຜົນໄດ້ຮັບສະບັບປັບປຸງ: 0, Checksum: 3

ແຜນທີ່ {1 = 1, 2 = 1}, ເວລານີ້ພວກເຮົາຍັງເພີ່ມມູນຄ່ານັ້ນກັບການປະກົດຕົວຂອງມັນເຂົ້າໃນແຜນທີ່.

  • ສໍາຫລັບ 2nd ອົງປະກອບ, ການປະຕິບັດງານດຽວກັນທີ່ໄດ້ເຮັດມາກ່ອນ, ໃນເວລານີ້ມັນພົບວ່າອົງປະກອບເປັນ [i] -1 ແລະພວກເຮົາໄດ້ຮັບຜົນຜະລິດທີ່ປັບປຸງ ໃໝ່:

ຜົນໄດ້ຮັບສະບັບປັບປຸງ: 2, Checksum: 6

ແຜນທີ່ {1 = 1, 2 = 1, 3 = 1}, ເພີ່ມສ່ວນປະກອບແລະຄວາມຖີ່ຂອງມັນ.

  • ສຳ ລັບອົງປະກອບທີ 3, ມັນພໍໃຈກັບອັນທີສອງຖ້າ ຄຳ ຖະແຫຼງ, ໝາຍ ຄວາມວ່າມັນປະຕິບັດຕາມຖ້າແຜນທີ່ມີຄ່າ [i] +1, ຫຼັງຈາກນັ້ນພວກເຮົາໄດ້ຮັບຜົນຜະລິດທີ່ຖືກປັບປຸງ:

ຜົນໄດ້ຮັບສະບັບປັບປຸງ: 0, Checksum: 7, ແຜນທີ່: {1 = 2, 2 = 1, 3 = 1}

  • ສຳ ລັບສ່ວນປະກອບທີ 4, ຫຼັງຈາກຜ່ານບົດຖະແຫຼງການ ທຳ ອິດຖ້າ.

ຜົນໄດ້ຮັບສະບັບປັບປຸງ: 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, ດັ່ງນັ້ນຄວາມສັບສົນໃນອະວະກາດຈຶ່ງເປັນເສັ້ນ.