ຈຳ ນວນຕົວເລກສູງສຸດທີ່ສະ ເໜີ ໃນ Array  


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

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

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

ຍົກຕົວຢ່າງ  

arr[] = {2, 24, 30, 26, 99, 25}
3

ຄໍາອະທິບາຍ: ຕົວເລກທີ່ຕິດຕໍ່ກັນແມ່ນ⇒ 24, 25, 26 (ຊຸດຂອງ 3).

arr[] = { -8, 9 , -1, -6, -5}
2

ຄໍາອະທິບາຍ: ຕົວເລກທີ່ຕິດຕໍ່ກັນແມ່ນ⇒ -6, -5 (ຊຸດຂອງ 2).

ລະບົບວິເຄາະ  

1. Declare a set.
2. Do traversing of the array, and insert all the values of array into the Set.
3. Set output to 0.
4. Traverse the array from i=0, to i<n(length of the array).
  1. Check if Set contains the arr[i].
    1. If true, then pick the current array element and store it to temp.
  2. While Set contains the temp, repeatedly increases the values of temp.
  3. Find out the maximum between output and temp-arr[i] and store it into the output.
5. Return output.

ຄໍາອະທິບາຍ  

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

ເບິ່ງ
ພິມທຸກສ່ວນທີ່ມີຄວາມແຕກຕ່າງຂອງຕົວເລກລວມຕົວໃຫ້

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

ດຽວນີ້ພວກເຮົາຕ້ອງຊອກຫາຜົນຜະລິດສູງສຸດແລະຄວາມແຕກຕ່າງຂອງ temp-arr [i], ຢ່າຄິດວ່າຖ້າຄວາມແຕກຕ່າງນີ້ເຮັດໃຫ້ຕົວເລກທີ່ບໍ່ຖືກຕ້ອງຂອງ ຈຳ ນວນດັ່ງທີ່ພວກເຮົາຈະໄດ້ຮັບຄ່າເພີ່ມຂອງ temp ໃນຂະນະທີ່ອອກ loop, ພວກເຮົາຈະໄດ້ຮັບຕົວເລກທີ່ຖືກຕ້ອງຂອງຕົວເລກຕໍ່ເນື່ອງໃນປະຈຸບັນ. ພວກເຮົາຈະເກັບສູງສຸດລະຫວ່າງຜົນຜະລິດແລະຄວາມແຕກຕ່າງຂອງ temp-arr [i] (ຜົນຜະລິດ, temp-arr [i]). Arr [i] ແມ່ນພຽງແຕ່ຈຸດເລີ່ມຕົ້ນຂອງຊຸດຂອງຕົວເລກແລະໄລຍະເວລາຕິດຕໍ່ກັນ, ຈຸດຈົບ. ຂັ້ນຕອນເຫຼົ່ານີ້ຈະຖືກເຮັດຊ້ ຳ ອີກຈົນກ່ວາພວກເຮົາໄດ້ພົບເຫັນຜົນຜະລິດສູງສຸດຫລັງຈາກທີ່ ກຳ ລັງຜ່ານແຖວທັງ ໝົດ.

ຈຳ ນວນຕົວເລກສູງສຸດທີ່ສະ ເໜີ ໃນ ArrayPin

ການປະຕິບັດ  

ໂປແກຼມ C ++ ເພື່ອຊອກຫາຕົວເລກທີ່ສູງສຸດທີ່ສະແດງໃນ Array

#include<iostream>
#include<unordered_set>

using namespace std;

int getMaxConsecutiveNumber(int arr[], int n)
{
    unordered_set<int> SET;
    for (int i = 0; i < n; i++)
        SET.insert(arr[i]);

    int output = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr[i] - 1) == SET.end())
        {
            int temp = arr[i];

            while (SET.find(temp) != SET.end())
                temp++;

            output = max(output, temp - arr[i]);
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 24, 30, 26, 99, 25 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Largest Set found : "<<getMaxConsecutiveNumber(arr, n)<< endl;
    return 0;
}
Largest Set found : 3

ໂປຣແກຣມ Java ເພື່ອຊອກຫາຕົວເລກທີ່ສາມາດຕັດຕໍ່ໄດ້ສູງສຸດໃນ Array

import java.util.HashSet;

class LargestConsecutiveSet
{
    public static int getMaxConsecutiveNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
        }
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if(SET.contains(arr[i]))
            {
                int temp = arr[i];
                while (SET.contains(temp))
                    temp ++;

                output = Math.max(output, temp - arr[i]);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2, 24, 30, 26, 99, 25};
        int n = arr.length;
        System.out.println("Largest Set found : "+getMaxConsecutiveNumber(arr, n));
    }
}
Largest Set found : 3

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການຊອກຫາຕົວເລກທີ່ມີຕົວເລກສູງສຸດທີ່ມີຢູ່ໃນ Array  

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ໃຊ້ HashSet, ເຊິ່ງຊ່ວຍໃຫ້ການແຊກ, ການລຶບ, ແລະການຄົ້ນຫາໃນເວລາຄົງທີ່.

ເບິ່ງ
ປ່ຽນສອງຄ່າທີ່ມີຄ່າເທົ່າກັນຕິດຕໍ່ກັນກັບ ໜຶ່ງ ທີ່ໃຫຍ່ກວ່າ

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ພວກເຮົາໄດ້ເກັບຮັກສາອົງປະກອບ N ໄວ້ໃນສະລັບສັບຊ້ອນພື້ນທີ່ເປັນເສັ້ນ.

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