მასივში წარმოდგენილი ზედიზედ მაქსიმალური რიცხვები


Რთული ტური Easy
ხშირად ეკითხებიან თანამოსაყრელი Adobe Amazon Fourkites MAQ
Array Hash

პრობლემის განცხადება

დავუშვათ, რომ მასივი გაქვთ რიცხვები ზომის 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.

განმარტება

მოცემული ან მთელი რიცხვი მასივი, ჩვენ უნდა გავარკვიოთ მასივში არსებული თანმიმდევრული რიცხვების უმაღლესი რაოდენობა. ჩვენ ვაპირებთ გამოვიყენოთ ა მითითებული. ნაკრები გთავაზობთ მსგავსი ელემენტის ამოღების მახასიათებელს. ასე რომ, ჩვენ არ უნდა ვიდარდოთ სახელურის საერთო ელემენტზე, ის ავტომატურად დამუშავდება.

ჩვენ ვაწყდებით მასივის ყველა მნიშვნელობის დამატებაში. რადგან მოგვიანებით, ჩვენ ვაპირებთ ზედიზედ ციფრების შემოწმებასაც. ჩვენ კვლავ გადავკვეთთ მასივს, ავირჩევთ თითოეულ ელემენტს და ვამოწმებთ არის თუ არა ეს ელემენტი რუკა აქვს arr [i], თუ სიმართლეა, ჩვენ ვაპირებთ ამ ელემენტის აყვანას დროებით ცვლადში და ვამოწმებთ ისევ თუ რუქა შეიცავს ამ ტემპს, თუ ასეა, შემდეგ გაზრდის temp- ის მნიშვნელობას 1-ით, შემდეგ კი ისევ ვამოწმებთ და ისევ გაზრდის მას, განაგრძობს ამას მანამ, სანამ რუკას არ ექნება ამ გაზრდილი მნიშვნელობა. ახლა, როდესაც ამ მარყუჟიდან გამოვალთ, ჩვენ ვიხილავთ მასივის ამჟამინდელი ელემენტის ყველაზე მეტ მნიშვნელობას, რომელიც მოცემულია რუქაზე, ამასთან, მას ვზრდით 1-ით, ასე რომ, ის ასევე იქნება თანმიმდევრული რიცხვები.

ახლა ჩვენ უნდა გავარკვიოთ გამოტანის მაქსიმუმი და temp-arr- ის სხვაობა [i], არ იფიქროთ ისე, თითქოს ეს სხვაობა იძლევა რიცხვის არასწორ რაოდენობას, რადგან მივიღებთ 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

ჯავა პროგრამა მასივში წარმოდგენილი ზედიზედ მაქსიმალური რიცხვების მოსაძებნად

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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. რადგან ჩვენ გამოვიყენეთ HashSet, რაც საშუალებას გაძლევთ ჩასმა, წაშლა და ძებნის ოპერაცია მუდმივ დროში.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ჩვენ გვაქვს შენახული N ელემენტები, ამრიგად ხაზოვანი სივრცის სირთულე.

Reference