Дар массив калонтарин d-ро тавре ёбед, ки a + b + c = d


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Accolite Amazon Деҳлӣ Фараж Фуркайтҳо FreeCharge
тартиботи ҳарбӣ Хаш

Изҳороти мушкилот

Фарз мекунем, ки шумо як асал of ҳаждаҳҳо. Арзишҳои вуруд ҳама унсурҳои алоҳида мебошанд. Масъалаи "Дар массиви d калонтаринро пайдо кунед, ки a + b + c = d" дархост кунад, ки бузургтарин 'd' -ро дар маҷмӯъ тавре муайян кунед, ки a + b + c = d, ки дар он ҳамаи элементҳо аз ҳамдигар фарқ доранд.

мисол

arr[] = {1, 4, 6, 8, 11 }
11

Шарҳ: Се рақами a, b ва c 1, 4 ва 6 мебошанд ва ҷамъи онҳо 11 мебошад.

arr[] = {2,4,6,10,15 }
No such solution exists.

Шарҳ: Азбаски се рақам вуҷуд надорад, ин рақамро ҷамъ мекунад.

Алгоритм

1. Declare a Map.
2. While traversing through the array.
    1. Add and insert the sum of two elements in a map with their indexes in a Map.
3. Set the number to the minimum value of an integer, which we have to find out.
4. Search for the third number in a map by checking the difference of two numbers is present in a map.
5. If true then check if their indexes should not be the same.
6. Check for the maximum of d and the maximum of arr[i] and arr[j] and store it to d.
7. Return d.

Шарҳ

Биёед як ҳамаҷониба асал иборат аз бутунҳои алоҳида. Вазифаи мо иборат аз он аст, ки рақамро тавре пайдо кунем, ки се рақам вуҷуд дошта бошад, ки ба ин рақам ҷамъбаст карда шаванд. Мо истифода бурданием Хашм. Хешкунӣ ҳалли муассирро таъмин мекунад. Массивро тай кунед ва дар як вақт ду унсури массивро гиред ва маблағи он ҷуфтҳоро барои индексҳои мувофиқашон нигоҳ доред.

Мо ҷуфтро нигоҳ медорем, зеро мо d -ро ҷустуҷӯ карда истодаем, ба тавре ки a + b + c = d. Ба ҷои ин, мо ҷустуҷӯи a + b = d - c хоҳем буд. Ҳамин тавр, дар аввал, вақте ки мо ҷуфт ва нишондиҳандаҳои онҳоро нигоҳ медорем. Мо метавонем унсури 'd' -ро тафтиш кунем, ки d - c дар харита мавҷуд бошад. Инро бо роҳи убур кардани массив ва сипас якбора ду элемент гирифтан мумкин аст. Фарқияти ҳарду унсурро фарқ кунед ва ин фарқиятро ҷустуҷӯ кунед, агар дар харита мавҷуд бошад. Агар ин дуруст бошад, санҷед ду унсури ҳозира набояд дар як индекс бо ҷуфтҳои пешинаи индекс бошанд.

Ин бояд тафтиш кард, ки оё ягон унсур набояд дар як нишондиҳанда такрор карда шавад, шумораи такроршавандаро дар а, б, в ва d баррасӣ кардан мумкин аст, аммо нишондиҳандаҳои онҳо, ба маънои он, ки худи рақам дар ҳамон нишондиҳанда бошад ба назар гирифта намешавад. Аз ин рӯ, мо бояд ин плагиатро нишон диҳем. Ҳоло, ба мо лозим аст, ки ҳадди аксар arr [i] ва arr [j] -ро муайян намоем ва ин d максимумро ба d санҷем, то ҳадди аксарро байни онҳо фаҳмида то d нигоҳ дорем. Зеро, мо бояд рақами чоруми d-ро муайян кунем, бинобар ин мо бояд максимум элементҳои массивро ёбем, зеро d дар байни a, b, c ва d ҳамеша бузургтар аст.

татбиќи

Барномаи C ++ барои ёфтани d калонтаринро дар массива, ба монанди a + b + c = d

#include<iostream>
#include<unordered_map>

using namespace std;

int getSumThreeNumber(int arr[], int n)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            MAP[arr[i] + arr[j]] = { i, j };
        }
    }
    int d_number = INT_MIN;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int third = abs(arr[i] - arr[j]);

            if (MAP.find(third) != MAP.end())
            {
                pair<int, int> obj = MAP[third];
                if (obj.first != i && obj.first != j && obj.second != i && obj.second != j)
                    d_number = max(d_number, max(arr[i], arr[j]));
            }
        }
    }
    return d_number;
}
int main()
{
    int arr[] = { 1,4,6,8,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = getSumThreeNumber(arr, n);
    if (res == INT_MIN)
        cout << "No such solution exists";
    else
        cout << res;
    return 0;
}
11

Барномаи Java барои ёфтани d калонтаринро дар массива ба тавре ки a + b + c = d

import java.util.HashMap;

class CheckIndex
{
    int i, j;

    CheckIndex(int i, int j)
    {
        this.i = i;
        this.j = j;
    }
    int checkI()
    {
        return i;
    }

    int checkJ()
    {
        return j;
    }
}

class sumOfThreeElementToD
{

    public static int getSumThreeNumber(int[] arr, int n)
    {
        HashMap<Integer, CheckIndex> map = new HashMap<>();

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                map.put(arr[i] + arr[j], new CheckIndex(i, j));
            }
        }

        int d_number = Integer.MIN_VALUE;

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int third = Math.abs(arr[i] - arr[j]);

                if (map.containsKey(third))
                {
                    CheckIndex ci = map.get(third);
                    if (ci.checkI() != i && ci.checkI() != j && ci.checkJ() != i && ci.checkJ() != j)
                    {
                        d_number = Math.max(d_number, Math.max(arr[i], arr[j]));
                    }
                }
            }
        }
        return d_number;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 8, 11 };
        int n = arr.length;
        int output = getSumThreeNumber(arr, n);
        if (output == Integer.MIN_VALUE)
            System.out.println("No such solution exists");
        else
            System.out.println(output);
    }
}
11

Таҳлили мураккабӣ барои ёфтани d-и калонтарин ба дараҷае, ки a + b + c = d

Мураккабии вақт

О (н2ки дар "Н" шумораи унсурҳои массив аст. Мо ба ин мураккабӣ ноил шудем, зеро мо HashMap -ро истифода кардем, ки ҷустуҷӯи дохилкунӣ ва амалиётҳои дигарро дар вақти O (1) имкон медиҳад.

Мураккабии фазо

О (н2) ки дар "Н" шумораи унсурҳои массив аст. Азбаски HashMap иловаҳои ҷуфти унсурҳои гуногуни вурудро нигоҳ медорад. Аз ин сабаб, алгоритм мураккабии фазои квадратиро дорад.

ишора