ຄວາມແຕກຕ່າງກັນສູງສຸດລະຫວ່າງດັດສະນີ ທຳ ອິດແລະສຸດທ້າຍຂອງອົງປະກອບ ໜຶ່ງ ໃນຂບວນ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Amazon hike MakeMyTrip Ola Cabs ຫ້ອງທົດລອງ SAP
Array Hash

ສົມມຸດວ່າ, ເຈົ້າມີ array of integers. ບັນຫາ "ຄວາມແຕກຕ່າງສູງສຸດລະຫວ່າງດັດສະນີ ທຳ ອິດແລະສຸດທ້າຍຂອງອົງປະກອບທີ່ຢູ່ໃນຂບວນ" ຂໍໃຫ້ຄົ້ນພົບຄວາມແຕກຕ່າງລະຫວ່າງດັດສະນີ ທຳ ອິດແລະສຸດທ້າຍຂອງແຕ່ລະຕົວເລກທີ່ມີຢູ່ໃນຂບວນດັ່ງກ່າວວ່າຄວາມແຕກຕ່າງແມ່ນສູງສຸດຂອງທຸກໆຢ່າງ.

ຍົກຕົວຢ່າງ

arr[] =  {2, 3, 5, 1, 4, 6, 2, 5};
6

ຄໍາອະທິບາຍ

2 ດັດສະນີ ທຳ ອິດ→ 0

2 ຂອງດັດຊະນີສຸດທ້າຍ→ 6

ຄວາມແຕກຕ່າງສູງສຸດ (6-0) = 6

ຄວາມແຕກຕ່າງກັນສູງສຸດລະຫວ່າງດັດສະນີ ທຳ ອິດແລະສຸດທ້າຍຂອງອົງປະກອບ ໜຶ່ງ ໃນຂບວນ

arr[] =  {2, 3, 6, 5, 4, 5, 1, 4};
3

ຄໍາອະທິບາຍ

4 ດັດສະນີ ທຳ ອິດ→ 4

4 ຂອງດັດຊະນີສຸດທ້າຍ→ 7

ຄວາມແຕກຕ່າງສູງສຸດ (7-4) = 3

ລະບົບວິເຄາະ

  1. ລອກເອົາທັງ ໝົດ array.
  2. ເອົາແຕ່ລະອົງປະກອບຂອງອາເລແລະເອົາອົງປະກອບ ທຳ ອິດແລະສຸດທ້າຍຂອງມັນໄປເກັບໄວ້ໃນ HashTable.
  3. Traverse ໄດ້ ແຜນທີ່:
    1. ຊອກຮູ້ຄວາມແຕກຕ່າງລະຫວ່າງດັດສະນີ ທຳ ອິດແລະດັດຊະນີສຸດທ້າຍຂອງແຕ່ລະອົງປະກອບ.
    2. ເກັບຄວາມແຕກຕ່າງສູງສຸດເຂົ້າໃນບາງຕົວແປແລະສືບຕໍ່ປັບປຸງ ໃໝ່ ທຸກຄັ້ງທີ່ທ່ານພົບວ່າມີຄຸນຄ່າສູງສຸດທຽບໃສ່ຄ່າທີ່ຜ່ານມາ.
  4. ສົ່ງຄືນຄວາມແຕກຕ່າງສູງສຸດ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ຮັບ integer array, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຮູ້ຄວາມແຕກຕ່າງລະຫວ່າງດັດສະນີ ທຳ ອິດແລະດັດຊະນີສຸດທ້າຍຂອງແຕ່ລະຄ່າຂອງອາເລ. ຊອກຫາຄວາມແຕກຕ່າງສູງສຸດ ສຳ ລັບ ຈຳ ນວນໃດ ໜຶ່ງ ລະຫວ່າງດັດຊະນີ ທຳ ອິດແລະຄັ້ງສຸດທ້າຍ. ສຳ ລັບສິ່ງນີ້, ພວກເຮົາ ກຳ ລັງຈະ ນຳ ໃຊ້ ແຮກ. ພວກເຮົາຈະເອົາອົງປະກອບທີ່ເປັນຂບວນແລະຈະຊອກຫາດັດສະນີແລະດັດສະນີ ທຳ ອິດຫລືເມື່ອມັນເກີດຂື້ນໃນຄັ້ງ ທຳ ອິດແລະສຸດທ້າຍ.

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

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

ຍົກຕົວຢ່າງ

ຮອດ [] = {2, 3, 5, 1, 4, 6, 2, 5}

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

ແຜນທີ່: 1-> 3: ບໍ່,

2-> 0: 6, ທ.

3-> 1, ບໍ່,

4-> 4: ບໍ່,

5-> 2: 7, ທ.

6-> 5: ບໍ່

ພວກເຮົາຈະຂ້າມຜ່ານແຜນທີ່, ແລະພວກເຮົາຈະເອົາແຕ່ລະຄ່າແລະກວດກາຄວາມແຕກຕ່າງຂອງຕົວຊີ້ວັດຂອງພວກມັນ. ພວກເຮົາຈະລະເລີຍທຸກໆຄຸນຄ່າທີ່ມີຄ່າບໍ່ມີຄ່າ. ດັ່ງນັ້ນພວກເຮົາມີ 2 ແລະ 5 ແລະນອກຈາກນັ້ນ 2 ມີຄວາມແຕກຕ່າງກັນສູງສຸດ (6) ລະຫວ່າງດັດຊະນີ ທຳ ອິດແລະຄັ້ງສຸດທ້າຍກ່ວາ 5 ເຊິ່ງມີຄວາມແຕກຕ່າງ (5). ດັ່ງນັ້ນພວກເຮົາຈະກັບຄືນ 6 ອັນທີ່ແຕກຕ່າງກັນສູງສຸດແລະນັ້ນກໍ່ແມ່ນ ຄຳ ຕອບຂອງພວກເຮົາ.

ລະຫັດ C ++ ເພື່ອຊອກຫາຄວາມແຕກຕ່າງສູງສຸດລະຫວ່າງດັດສະນີ ທຳ ອິດແລະຄັ້ງສຸດທ້າຍຂອງອົງປະກອບທີ່ຢູ່ໃນຂບວນ

#include<bits/stdc++.h>

using namespace std;

int maxDifference(int arr[], int n)
{
    struct IndexValue
    {
        int fir, last;
    };
    unordered_map<int, IndexValue> MAP;
    for (int i=0; i<n; i++)
    {
        if (MAP.find(arr[i]) == MAP.end())
            MAP[arr[i]].fir = i;

        MAP[arr[i]].last = i;
    }

    int difference, differenceIndex = INT_MIN;

    unordered_map<int, IndexValue>::iterator itr;
    for (itr=MAP.begin(); itr != MAP.end(); itr++)
    {
        difference = (itr->second).last - (itr->second).fir;
        if (differenceIndex < difference)
            differenceIndex = difference;
    }
    return differenceIndex;
}
int main()
{
    int arr[] = {2, 3, 5, 1, 4, 6, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference b/w the first and last index of a number= "<<maxDifference(arr, n);
    return 0;
}
Maximum difference b/w the first and last index of a number= 6

ລະຫັດ Java ເພື່ອຊອກຫາຄວາມແຕກຕ່າງກັນສູງສຸດລະຫວ່າງດັດສະນີ ທຳ ອິດແລະສຸດທ້າຍຂອງອົງປະກອບທີ່ຢູ່ໃນຂບວນ

import java.util.HashMap;
import java.util.Map;

class IndexValue
{
    int first;
    int second;
    public IndexValue()
    {
        super();
    }
}
class DifferenceOfIndexes
{
    private static int getIndexesDifferent(int[] arr)
    {
        int n = arr.length;
        int differenceIndex = 0;
        Map<Integer, IndexValue> MAP = new HashMap<Integer, IndexValue>();

        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]))
            {
                IndexValue iv = MAP.get(arr[i]);
                iv.second = i;
            }
            else
            {
                IndexValue iv = new IndexValue();
                iv.first = i;
                MAP.put(arr[i], iv);
            }
        }
        for (Map.Entry<Integer, IndexValue> entry : MAP.entrySet())
        {
            IndexValue iv = entry.getValue();
            if ((iv.second - iv.first) > differenceIndex)
            {
                differenceIndex = iv.second - iv.first;
            }
        }
        return differenceIndex;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,5,1,4,6,2,5};
        System.out.println("Maximum difference b/w the first and last index of a number= "+ getIndexesDifferent(arr));
    }
}
Maximum difference b/w the first and last index of a number= 6

ການວິເຄາະຄວາມສັບສົນ

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

O (n) ບ່ອນທີ່ “ n ' ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ

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

O (n) ບ່ອນທີ່ “ n ' ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ