Массив дахь дараалсан хамгийн их тоо


Хэцүү байдлын түвшин Easy
Байнга асуудаг Accolite Adobe Амазоны Фуркайт MAQ
Array Хаш

Асуудлын мэдэгдэл

Танд массив байна гэж бодъё бүхэл тоо хэмжээтэй 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.

Тайлбар

Өгсөн бүхэл тоо массив, бид массивт байгаа дараалсан тоонуудын хамгийн их тоог олох ёстой. Бид ашиглах болно багц. Set нь ижил төстэй элементийг арилгах боломжийг олгодог. Тиймээс бид нийтлэг элементийн бариулын талаар санаа зовох хэрэггүй бөгөөд үүнийг автоматаар зохицуулах болно.

Бид массивын бүх утгыг Set дээр нэмэх гэж байна. Учир нь дараа нь бид дараалсан дугааруудыг бас шалгах болно. Бид массивыг дахин туулж элемент бүрийг сонгож, эсэхийг шалгана газрын зураг Хэрэв [i] гэсэн arr байгаа бол бид тухайн элементийг түр зуурын хувьсагч болгон сонгож, газрын зураг дээрх temp-ийг агуулсан бол дахин шалгаж, temp-ийн утгыг 1-ээр нэмэгдүүлээд дараа нь дахин шалгаж, дахин өсгөж, газрын зураг дээр ийм нэмэгдсэн утга байхгүй болтол үргэлжлүүлнэ. Одоо бид энэ давталтаас гарч ирэхэд газрын зурагт байгаа массивын хамгийн их өссөн утгыг өгөх болно, мөн үүнийг 1-ийн тоогоор нэмэгдүүлэх тул энэ нь бас дараалсан тоо байх болно.

Бид одоо гаралтын дээд хэмжээ болон temp-arr-ийн зөрүүг олох ёстой [i], энэ ялгаа нь тооллын буруу тоог өгдөг гэж битгий бодоорой, учир нь temp-ийн гарч ирэх үед нэмэгдсэн temp утгыг авна. давталт, бид одоо байгаа дараалсан тооны зөв тоог авах болно. Дараа нь бид гаралт ба temp-arr [i] (гаралт, temp-arr [i]) -ийн зөрүүг хамгийн их байлгах болно. Arr [i] нь дараалсан тооны цуврал ба түр зуурын төгсгөлийн цэгийн эхлэх цэг юм. Бүх массивыг дайран өнгөрсний дараа хамгийн их гаралтыг олох хүртэл эдгээр алхмуудыг давтах болно.

Массив дахь дараалсан хамгийн их тоо

Хэрэгжүүлэх

Массивт байгаа дараалсан хамгийн их тоог олох C ++ програм

#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 програм

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

Массивт байгаа дараалсан хамгийн их тоонуудыг олох нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм. Учир нь бид оруулах, устгах, хайлт хийх үйлдлийг тогтмол хугацаанд хийдэг HashSet-ийг ашигласан болно.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм. Бид N элементийг багцад хадгалсан тул шугаман орон зайн нарийн төвөгтэй байдал.

лавлагаа