Массивден a + b + c = d чоңдугун көрсөткөндөй ири d табыңыз


Кыйынчылык деңгээли орто
Көп суралган Accolite Amazon Delhivery динчилдер Fourkites FreeCharge
согуштук тизме таштанды

Маселени билдирүү

Сизде ан бар дейли согуштук тизме of бүтүн. Киргизилген маанилердин бардыгы айырмаланган элементтер. Массивден "a + b + c = d турган ири d табуу" маселеси, бардык элементтер бири-биринен айырмаланган, a + b + c = d чоңдуктагы 'd' элементин табууну сурайт.

мисал

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

Explanation: Үч a, b жана c сандары 1, 4 жана 6 жана алардын суммасы 11.

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

Explanation: Үч сан жок болгондуктан, ал бир санга чейин чыгат.

Algorithm

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.

түшүндүрүү

Карап көрөлү бүтүн согуштук тизме так сандардан турат. Биздин милдет - санды ушундайча жол менен табуу, ал санга үч сан бар. Биз колдоно турган болдук Hashing. Hashing натыйжалуу чечим берет. Массивди айланып өтүп, бир эле учурда эки массивдин элементтерин алып, ошол жуптардын суммасын тиешелүү индекстер менен картага түшүрүү үчүн сактаңыз.

Биз жупту сактайбыз, анткени a + b + c = d деп d издеп жатабыз. Мунун ордуна биз a + b = d - c деп издейбиз. Ошентип, алгач жупту жана алардын индекстерин сактаганда. Картада d - c бар болгон 'd' элементин текшере алабыз. Бул массивди аралап өтүп, андан кийин бир эле учурда эки элементти тандап алса болот. Эки элементтин тең айырмасын түзүңүз жана картада бар болсо, ошол айырманы издеңиз. Эгер бул чын деп табылса, анда учурдагы эки элемент индекстеги мурунку түгөйлөр менен бирдей индексте болбошу керек экендигин текшериңиз.

Бул элементтердин кайсынысы бир эле индексте кайталанбашы керектигин текшерүү үчүн керек, кайталанган санды a, b, c жана d деп эсептөөгө болот, бирок алардын индекстери, ошол эле индекстеги сандын өзү каралбайт. Демек, биз ал индекстердин плагиат экендигин текшеришибиз керек. Эми, arr [i] жана arr [j] максимумун аныктап, d максимумун текшерип, алардын ортосундагы максимумду билип, d ге чейин сакташыбыз керек. Анткени, төртүнчү санды табышыбыз керек, андыктан массив элементтеринин максимумун табышыбыз керек, анткени d a, b, c жана d арасында ар дайым чоңураак.

ишке ашыруу

Массивдеги эң чоң dди табуу үчүн C ++ программасы, 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

A + b + c = d массивиндеги эң чоң d табуучу Java программасы

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 болгондой

Убакыт татаалдыгы

O (n2кайда "N" массивдеги элементтердин саны. Биз бул татаалдыкка жетиштик, анткени O (1) убакыттын ичинде издөө жана башка операцияларды жүргүзүүгө мүмкүнчүлүк берген HashMap колдондук.

Космостун татаалдыгы

O (n2) кайда "N" массивдеги элементтердин саны. HashMap кириштин ар кандай элементтеринин жуптарын сактагандыктан. Мындан улам, алгоритм квадраттык мейкиндиктин татаалдыгына ээ.

шилтеме