ໄລຍະຫ່າງສູງສຸດລະຫວ່າງສອງເຫດການທີ່ເກີດຂື້ນຂອງອົງປະກອບດຽວກັນໃນອາເລ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ເດລີ ປັດໃຈ ສະ ເໜ່ ສີ່ພັນ
Array Hash

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

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ:

array = [1, 2, 3, 6, 2, 7]

ຜົນໄດ້ຮັບ:

3

ຄໍາອະທິບາຍ:

ເນື່ອງຈາກວ່າອົງປະກອບທີ່ array [1] ແລະ array [4] ມີອົງປະກອບດຽວກັນທີ່ເປັນ '2' ທີ່ມີໄລຍະຫ່າງສູງສຸດ 3.

ການປ້ອນຂໍ້ມູນ:

array = [3, 4, 6, 7, 4, 8, 9, 3]

ຜົນໄດ້ຮັບ:

7

ຄໍາອະທິບາຍ:

ເນື່ອງຈາກວ່າ array array [0] ແລະ array [7] ມີອົງປະກອບດຽວກັນທີ່ເປັນ '3' ທີ່ມີໄລຍະຫ່າງສູງສຸດ 3.

ສູດການຄິດໄລ່ ສຳ ລັບໄລຍະຫ່າງສູງສຸດລະຫວ່າງສອງເຫດການທີ່ເກີດຂື້ນຂອງອົງປະກອບດຽວກັນ

  1. ປະກາດກ ແຜນທີ່.
  2. ທີ່ກໍານົດໄວ້ “ maxDistance” to 0
  3. ໃນຂະນະທີ່ຂ້ອຍນ້ອຍກວ່າຄວາມຍາວຂອງອາເລ (n).
    1. ກວດເບິ່ງແຕ່ລະອົງປະກອບຖ້າມັນມີການປະກົດຕົວຄັ້ງ ທຳ ອິດຫຼືບໍ່ຢູ່ໃນແຜນທີ່, ຖ້າ ທຳ ອິດ,
      1. ຈາກນັ້ນໃສ່ອົງປະກອບແລະດັດສະນີຂອງມັນລົງໃນແຜນທີ່.
    2. ອື່ນ (ຖ້າມັນມີຢູ່ແລ້ວ)
      1. ຊອກຫາໄລຍະທາງສູງສຸດລະຫວ່າງໂຕເກົ່າແລະໄລຍະນີ້ (ໄລຍະຫ່າງລະຫວ່າງດັດສະນີ).
      2. ເກັບໄລຍະທາງສູງສຸດໃຫ້ “ maxDistance”.
  4. Return “ maxDistance”.

ຄໍາອະທິບາຍ

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

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

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

ຍົກຕົວຢ່າງ

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

i = 0, ມາຮອດ [i] = 8 => myMap = {8: 0}

i = 1, ມາຮອດ [i] = 1 => myMap = {8: 0, 1: 1}

i = 2, ມາຮອດ [i] = 3 => myMap = {8: 0, 1: 1, 3: 2}

i = 3, ມາຮອດ [i] = 2 => myMap = {8: 0, 1: 1, 3: 2, 2: 3}

i = 4, ມາຮອດ [i] = 4 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}

i = 5, ມາຮອດ [i] = 1 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}, ນີ້ມັນຈະເຫັນຄວາມແຕກຕ່າງລະຫວ່າງດັດສະນີປັດຈຸບັນແລະດັດຊະນີກ່ອນ ໜ້າ ນີ້ຂອງ '1', (5-1 = 4), 4 ແມ່ນເກັບຢູ່ໃນ maxDistance.

i = 6, ມາຮອດ [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4} ນີ້ມັນຈະເຫັນຄວາມແຕກຕ່າງລະຫວ່າງດັດສະນີປັດຈຸບັນແລະດັດຊະນີກ່ອນ ໜ້າ ຂອງ ' 3 ', (6-2 = 4), ແຕ່ 4 ແມ່ນຢູ່ໃນ maxDistance ແລ້ວ, ສະນັ້ນມັນບໍ່ ສຳ ຄັນ.

i = 7, ມາຮອດ [i] = 6 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7}

i = 8, ມາຮອດ [i] = 7 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8}

i = 9, ມາຮອດ [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} ນີ້ມັນຈະພົບຄວາມແຕກຕ່າງລະຫວ່າງ ດັດຊະນີປັດຈຸບັນແລະດັດຊະນີກ່ອນ ໜ້າ ນີ້ຂອງ '3', (9-3 = 6), 6 ແມ່ນເກັບໄວ້ໃນ maxDistance.

i = 10, ມາຮອດ [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} ນີ້ມັນຈະພົບຄວາມແຕກຕ່າງລະຫວ່າງ ດັດຊະນີປັດຈຸບັນແລະດັດຊະນີກ່ອນ ໜ້າ ນີ້ຂອງ '1', (10-1 = 9), 9 ແມ່ນເກັບໄວ້ໃນ maxDistance.

ແລະພວກເຮົາກັບຄືນ maxDistance ຄືກັບ 9.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບໄລຍະຫ່າງສູງສຸດລະຫວ່າງສອງເຫດການທີ່ເກີດຂື້ນຂອງ Same Element ໃນອາເລ

#include<bits/stdc++.h>
using namespace std;

int getDistance(int arr[], int n)
{
    unordered_map<int, int> my_map;
    int maxDistance = 0;
    for (int i=0; i<n; i++)
    {
        if (my_map.find(arr[i]) == my_map.end())
            my_map[arr[i]] = i;
        else
            maxDistance = max(maxDistance, i - my_map[arr[i]]);
    }

    return maxDistance;
}
int main()
{
    int arr[] = {8, 1, 3, 2, 4, 1, 3, 6, 7, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getDistance(arr, n);
    return 0;
}
9

ໂປຣແກຣມ Java ສຳ ລັບໄລຍະຫ່າງສູງສຸດລະຫວ່າງສອງເຫດການທີ່ເກີດຂື້ນຂອງ Same Element ໃນອາເລ

import java.io.*;
import java.util.*;

class distanceBSameNumbers
{
    static int getDistance(int[] arr, int n)
    {
        HashMap<Integer,Integer> my_map = new HashMap<>();

        int maxDistance = 0;

        for (int i = 0; i < n; i++)
        {
            if (!my_map.containsKey(arr[i]))
                my_map.put(arr[i], i);

            else
                maxDistance = Math.max(maxDistance, i - my_map.get(arr[i]));
        }

        return maxDistance;
    }
    public static void main(String args[])
    {
        int arr[] = {8,1,3,2,4,1,3,6,7,3,1};
        int n = arr.length;
        System.out.println(getDistance(arr, n));
    }
}
9

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບໄລຍະຫ່າງສູງສຸດລະຫວ່າງສອງເຫດການທີ່ເກີດຂື້ນຂອງອົງປະກອບດຽວກັນໃນອາເລ

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

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

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

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