একটি অ্যারেতে সর্বাধিক ধারাবাহিক নম্বর উপস্থিত


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক ফোরকিটস ম্যাক
বিন্যাস কাটা

সমস্যা বিবৃতি

মনে করুন আপনার একটি অ্যারে আছে পূর্ণসংখ্যার আকারের এন। সমস্যাটি "একটি অ্যারে উপস্থিত থাকা সর্বাধিক ধারাবাহিক সংখ্যা" ক্রমবর্ধমান সংখ্যার সর্বাধিক গণনা যা অ্যারেতে ছড়িয়ে যেতে পারে তা জানতে চাইতে।

উদাহরণ

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.

ব্যাখ্যা

দেওয়া হয়েছে একটি পূর্ণসংখ্যা বিন্যাস, আমাদের একটি অ্যারে উপস্থিত থাকা টানা সংখ্যার সর্বোচ্চ গণনা খুঁজে বের করতে হবে। আমরা একটি ব্যবহার করতে যাচ্ছি সেট। সেট অনুরূপ উপাদান সরানোর বৈশিষ্ট্য সরবরাহ করে। সুতরাং, আমাদের সাধারণ উপাদানটির হ্যান্ডেল সম্পর্কে চিন্তা করার দরকার নেই, এটি স্বয়ংক্রিয়ভাবে পরিচালিত হবে।

আমরা অ্যারে সমস্ত মান যোগ করতে যাচ্ছি। কারণ পরবর্তীতে, আমরা পাশাপাশি পরপর সংখ্যাও পরীক্ষা করতে যাচ্ছি। আমরা প্রতিটি অ্যারে বাছাই করে আবার অ্যারেটি অতিক্রম করব এবং এটি পরীক্ষা করব মানচিত্র এর অ্যার [i] আছে, যদি সত্য হয় তবে আমরা সেই উপাদানটিকে একটি অস্থায়ী পরিবর্তনশীল হিসাবে বেছে নিতে যাচ্ছি এবং মানচিত্রটিতে যদি সেই টেম্পের উপস্থিত থাকে তবে আবার তা পরীক্ষা করে দেখি, তবে টেম্পের মান 1 করে বাড়িয়ে আবার পরীক্ষা করে দেখুন, এবং আবার এটি বৃদ্ধি করুন, মানচিত্রের সেই বর্ধিত মান না হওয়া পর্যন্ত এটি চালিয়ে যান। এখন, যখন আমরা এই লুপটি থেকে বেরিয়ে আসব, আমরা বর্তমান অ্যারে এলিমেন্টের সর্বাধিক বর্ধিত মান যা একটি মানচিত্রে উপস্থিত রয়েছে, আমরা এটি 1 এর গুণতেও বাড়িয়ে দেব, সুতরাং এটিও পরপর সংখ্যা হবে।

আমাদের এখন আউটপুট সর্বাধিক এবং টেম্প-আরারের পার্থক্য খুঁজে বের করতে হবে [i], ভাববেন না যে এই পার্থক্যটি গণনাটির ভুল সংখ্যা দেয় কারণ আমরা টেম্পের বর্ধিত মান পাব যখন বেরিয়ে আসার সময় লুপ, আমরা উপস্থিত টানা সংখ্যার সঠিক গণনা পেয়ে যাব। তারপরে আমরা আউটপুট এবং টেম্প-আরারের পার্থক্যের মধ্যে সর্বাধিক সংরক্ষণ করব [i] (আউটপুট, টেম্প-আরআর [i])। অর [i] একটানা সংখ্যা এবং টেম্পের, শেষের পয়েন্টের একটি সিরিজের কেবল একটি সূচনা পয়েন্ট। পুরো অ্যারেটি অতিক্রম করার পরে আমরা সর্বোচ্চ আউটপুট না পাওয়া পর্যন্ত এই পদক্ষেপগুলি পুনরাবৃত্তি করা হবে।

একটি অ্যারেতে সর্বাধিক ধারাবাহিক নম্বর উপস্থিত

বাস্তবায়ন

একটি অ্যারেতে সর্বাধিক ক্রমাগত সংখ্যাগুলি সন্ধান করতে সি ++ প্রোগ্রাম

#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

একটি অ্যারেতে সর্বাধিক ক্রমাগত সংখ্যাগুলি সন্ধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। কারণ আমরা হ্যাশসেট ব্যবহার করেছি যা স্থির সময়ে সন্নিবেশ, মোছা এবং অনুসন্ধানের ক্রিয়াকলাপটিকে অনুমতি দেয়।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। আমরা সেটগুলিতে এন উপাদানগুলিকে এইভাবে রৈখিক স্থান জটিলতা সংরক্ষণ করেছি।

উল্লেখ