Bir Arrayda göstərilən Maksimum Ardıcıl Nömrələr

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Çiy kərpic Amazon Fourkites MAQ
Geyim SükutBaxılıb 34

Problem bəyanat

Tutaq ki, sizdə bir sıra var tamsayılar ölçüsü N. problemi "Bir sıra içərisindəki maksimum ardıcıl ədədlər" bir sıra içərisinə səpələnə bilən ardıcıl sayların maksimum sayını tapmağı xahiş edir.

misal

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

Explanation: Ardıcıl rəqəmlər ⇒ 24, 25, 26 (3 dəsti).

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

Explanation: Ardıcıl rəqəmlər ⇒ -6, -5 (2 dəsti).

Alqoritm

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.

Izahat

Verilmiş bir tam array, bir sıra içərisindəki ardıcıl sayların ən yüksək sayını tapmalıyıq. A istifadə edəcəyik təyin etmək. Dəst bənzər bir elementi silmək xüsusiyyətini təqdim edir. Beləliklə, ümumi elementin sapı barədə narahat olmağımız lazım deyil, avtomatik olaraq həll ediləcəkdir.

Dəstin bütün dəyərlərini Dəstə əlavə edəcəyik. Çünki sonradan ardıcıl nömrələri də yoxlayacağıq. Hər bir elementi seçərək yenidən serialı keçəcəyik və əgər olmadığını yoxlayırıq xəritə o arr [i] var, doğrudursa, o elementi müvəqqəti dəyişən halına gətirəcəyik və bir xəritədə bu temp varsa yenidən yoxlayacağıq, əgər doğrudursa, temp dəyərini 1 artırın və sonra yenidən yoxlayın və yenidən artırın, xəritədə artan dəyəri olmayana qədər davam edir. İndi, bu döngədən çıxdıqda, xəritədə mövcud cari element elementinin ən çox artan dəyərini verəcəyik, onu 1 sayına qədər artırırıq, buna görə də ardıcıl ədədlər də olacaqdır.

İndi maksimum çıxışı və temp-arr [i] fərqini tapmaq məcburiyyətindəyik, sanki bu fərq saymanın səhv sayını verir deyə düşünməyin, çünki tempdən çıxarkən artan temp dəyərini alacağıq. loop, indiki ardıcıl sayların düzgün sayını alacağıq. Daha sonra çıxış və temp-arr [i] (output, temp-arr [i]) fərqi arasında maksimumu saxlayacağıq. Arr [i] ardıcıl ədədlər və temp, bitmə nöqtəsi üçün başlanğıc nöqtəsidir. Bu addımlar bütün massivi gəzdikdən sonra maksimum çıxışı tapana qədər təkrarlanacaqdır.

Bir Arrayda göstərilən Maksimum Ardıcıl NömrələrPin

Həyata keçirilməsi

Bir dizidə mövcud olan Maksimum Ardıcıl Nömrələri tapmaq üçün C ++ proqramı

#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

Bir serialda mövcud olan Maksimum Ardıcıl Nömrələri tapmaq üçün Java proqramı

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

Bir Dövrdə təqdim olunan Maksimum Ardıcıl Nömrələri tapmaq üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır. Sabit zamanda daxiletmə, silmə və axtarış əməliyyatına imkan verən HashSet istifadə etdik.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır. N elementini çoxluqda saxladıq, beləliklə xətti kosmik mürəkkəblik.

arayış

Translate »