ຊອກຫາ d ທີ່ໃຫຍ່ທີ່ສຸດໃນ Array ເຊັ່ນວ່າ a + b + c = d


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Amazon ເດລີ ສະ ເໜ່ ສີ່ພັນ FreeCharge
Array Hash

ຖະແຫຼງການບັນຫາ

ສົມມຸດວ່າທ່ານມີ array of integers. ຄ່າປ້ອນຂໍ້ມູນແມ່ນທຸກໆສ່ວນປະກອບທີ່ແຕກຕ່າງກັນ. ບັນຫາ“ ຊອກຫາ d ທີ່ໃຫຍ່ທີ່ສຸດໃນແຖວເຊັ່ນວ່າ a + b + c = 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.

ຄໍາອະທິບາຍ

ພິຈາລະນາເປັນ integer array ປະກອບດ້ວຍເລກເຕັມທີ່ແຕກຕ່າງກັນ. ວຽກງານຂອງພວກເຮົາແມ່ນເພື່ອຊອກຫາຕົວເລກໃນລັກສະນະດັ່ງກ່າວມີສາມຕົວເລກເຊິ່ງລວມເຖິງຕົວເລກນັ້ນ. ພວກເຮົາ ກຳ ລັງຈະໃຊ້ ແຮກ. Hashing ໃຫ້ການແກ້ໄຂທີ່ມີປະສິດຕິພາບ. ລອກແຖວອາເລແລະເອົາສອງອົງປະກອບຈັດລຽງລໍາດັບໃນເວລາດຽວກັນແລະເກັບຍອດລວມຂອງຄູ່ເຫຼົ່ານັ້ນເພື່ອວາງແຜນທີ່ມີດັດສະນີຂອງມັນ.

ພວກເຮົາຈະເກັບຮັກສາຄູ່ເພາະວ່າພວກເຮົາ ກຳ ລັງຊອກຫາ d, ເຊັ່ນວ່າ a + b + c = d. ແທນທີ່ຈະເປັນແນວນີ້, ພວກເຮົາຈະ ກຳ ລັງຄົ້ນຫາ a + b = d - c. ສະນັ້ນຕອນ ທຳ ອິດ, ເມື່ອພວກເຮົາເກັບຮັກສາຄູ່ແລະສະແດງຂອງພວກເຂົາ. ພວກເຮົາຈະສາມາດກວດສອບອົງປະກອບຂອງສິ່ງດັ່ງກ່າວທີ່ມີຢູ່ໃນແຜນທີ່. ນີ້ສາມາດເຮັດໄດ້ໂດຍຜ່ານການລ້ຽວແຖວອາເລ, ແລະຫຼັງຈາກນັ້ນຈັບສອງອົງປະກອບໃນເວລາດຽວກັນ. ສ້າງຄວາມແຕກຕ່າງຂອງທັງສອງອົງປະກອບແລະຄົ້ນຫາຄວາມແຕກຕ່າງນັ້ນຖ້າມີຢູ່ໃນແຜນທີ່. ຖ້າສິ່ງນີ້ພົບວ່າມັນເປັນຄວາມຈິງ, ໃຫ້ກວດເບິ່ງສອງປັດຈຸບັນນີ້ບໍ່ຄວນຢູ່ໃນດັດຊະນີດຽວກັນກັບຄູ່ກ່ອນ ໜ້າ ໃນດັດຊະນີ.

ນີ້ແມ່ນສິ່ງທີ່ ຈຳ ເປັນທີ່ຈະຕ້ອງກວດເບິ່ງວ່າອົງປະກອບໃດ ໜຶ່ງ ບໍ່ຄວນຖືກເຮັດ ໃໝ່ ໃນດັດຊະນີດຽວກັນ, ຕົວເລກທີ່ຊ້ ຳ ຊ້ອນສາມາດພິຈາລະນາໃນ a, b, c ແລະ d, ແຕ່ຕົວຊີ້ບອກຂອງມັນ, ໝາຍ ເຖິງເວົ້າ, ຕົວເລກຕົວມັນຢູ່ໃນດັດຊະນີດຽວກັນ ບໍ່ໄດ້ຮັບການພິຈາລະນາ. ດັ່ງນັ້ນພວກເຮົາຕ້ອງກວດເບິ່ງວ່າມີການລັກລອບເອົາຂໍ້ມູນເຫຼົ່ານັ້ນ. ດຽວນີ້, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາຈຸດສູງສຸດຂອງ arr [i] ແລະມາຮອດ [j] ແລະກວດເບິ່ງສູງສຸດນີ້ເພື່ອຊອກຫາຈຸດສູງສຸດລະຫວ່າງພວກມັນແລະເກັບມັນໄວ້ທີ່ d. ເນື່ອງຈາກວ່າ, ພວກເຮົາຕ້ອງຊອກຫາເລກທີສີ່ d, ສະນັ້ນພວກເຮົາຕ້ອງຊອກຫາສູງສຸດຂອງອົງປະກອບອາເລ, ເນື່ອງຈາກວ່າງແມ່ນມີຂະ ໜາດ ໃຫຍ່ກ່ວາ ໝູ່, a, b, c ແລະ d.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ເພື່ອຊອກຫາ d ທີ່ໃຫຍ່ທີ່ສຸດໃນ array ເຊັ່ນວ່າ 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 ທີ່ໃຫຍ່ທີ່ສຸດໃນ array ເຊັ່ນວ່າ 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

ການວິເຄາະຄວາມສັບສົນເພື່ອຊອກຫາທີ່ໃຫຍ່ທີ່ສຸດໃນ Array ເຊັ່ນວ່າ a + b + c = d

ຄວາມສັບສົນເວລາ

ໂອ (ນ2ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ພວກເຮົາໄດ້ບັນລຸຄວາມສັບສົນດັ່ງກ່າວເພາະວ່າພວກເຮົາໄດ້ໃຊ້ HashMap ເຊິ່ງຊ່ວຍໃຫ້ການຄົ້ນຫາແຊກແລະການປະຕິບັດງານອື່ນໆໃນເວລາ O (1).

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (ນ2) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ນັບຕັ້ງແຕ່ HashMap ເກັບເພີ່ມຄູ່ຂອງອົງປະກອບທີ່ແຕກຕ່າງກັນຂອງວັດສະດຸປ້ອນ. ເນື່ອງຈາກວ່ານີ້, ສູດການຄິດໄລ່ມີຄວາມສັບສົນພື້ນທີ່ສີ່ຫລ່ຽມ.

ກະສານອ້າງອີງ