দীর্ঘতম সুবরেতে কে-এর আলাদা আলাদা উপাদান নেই


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক দুর্গ Delhivery ফেসবুক মাইক্রোসফট স্যামসাং ইয়ানডেক্স
বিন্যাস কাটা সহচরী উইন্ডোতে

"দীর্ঘতম সাবমেরে কে স্বতন্ত্র উপাদানগুলির চেয়ে বেশি না থাকা" সমস্যাটি উল্লেখ করে যে ধরুন আপনার কাছে একটি বিন্যাস of পূর্ণসংখ্যার, সমস্যা বিবৃতিটি দীর্ঘতম উপ-অ্যারে খুঁজে বের করতে বলেছে যে K এর চেয়ে বেশি উপাদান নেই।

উদাহরণদীর্ঘতম সুবরেতে কে-এর আলাদা আলাদা উপাদান নেই

arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5}
k=3
2, 1, 2, 0

ব্যাখ্যা

কে স্বতন্ত্র উপাদানগুলির সাথে দীর্ঘতম উপ-অ্যারে (2, 1, 2, 0)

arr[] = {1, 2, 3, 4}
k=2
3, 4

ব্যাখ্যা

কে স্বতন্ত্র উপাদানগুলির সাথে দীর্ঘতম উপ-অ্যারে (3, 4)

অ্যালগরিদম

  1. প্রতিটি উপাদানের গণনা বাড়ান এবং রাখুন
  2. 0 থেকে শুরু করে কে এর চেয়ে বড় না হওয়া পর্যন্ত স্বতন্ত্র উপাদানগুলির একটি গণনা বজায় রাখুন।
  3. যদি গণনাটি কে-এর চেয়ে বেশি হয়ে যায়, তবে উপাদানগুলির গণনা হ্রাস শুরু করুন (সূচনা পয়েন্ট)।
  4. যতক্ষণ না আমরা আবার কে স্বতন্ত্র উপাদানগুলি উপ-অ্যারের প্রারম্ভিক বিন্দু বৃদ্ধি করি ততক্ষণ গণনা অপসারণ করতে থাকুন।
  5. দীর্ঘতম সাব-অ্যারে দৈর্ঘ্য পরীক্ষা করে অ্যারে উপাদান সূচক অনুযায়ী শেষটি আপডেট করুন।
  6. শেষ বিন্দু থেকে শুরু করে অ্যারে ফর্মটি মুদ্রণ করুন।

ব্যাখ্যা

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

আমাদের সেই জিনিসটির গণনাও বজায় রাখতে হবে যা নিশ্চিত করে যে কোনও সংখ্যা কে-এর চেয়ে বেশি হওয়া উচিত নয়। চল একটি উদাহরণ দিই:

অ্যার [] = {4, 3, 5, 2, 1, 2, 0, 4, 5}, কে = 3

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

যদি আমরা একটি অ্যারের থেকে 4, 3 এবং 5 বিবেচনা করি তবে আমাদের কাছে i = 2, কারার = 3 রয়েছে, আমরা পরবর্তী উপাদানটির জন্য গেলে আমরা 4 হিসাবে কারার পাই আমরা 2 টি উপ-অ্যারের প্রারম্ভিক পয়েন্ট হিসাবে পাই এবং আমাদের রাখা উচিত যতক্ষণ না আমরা কে স্বতন্ত্র উপাদানগুলির চেয়ে বেশি পেয়েছি।

কোড

সি ++ কোডে দীর্ঘতম সাবহারে কে স্বতন্ত্র উপাদানগুলির বেশি না রয়েছে তা সন্ধান করুন

#include<iostream>
#include<unordered_map>
using namespace std;

void getLongestSub(int arr[], int n, int k)
{
    unordered_map<int, int> count;

    int start = 0, endp = 0, curr = 0, left = 0;
    for (int i = 0; i < n; i++)
    {
        count[arr[i]]++;
        if (count[arr[i]] == 1)
            curr++;
        while (curr > k)
        {
            count[arr[left]]--;

            if (count[arr[left]] == 0)
                curr--;

            left++;
        }
        if (i - left + 1 >= endp - start + 1)
        {
            endp = i;
            start = left;
        }
    }
    for (int i = start; i <= endp; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getLongestSub(arr, n, k);
    return 0;
}
2 1 2 0

জাভা কোডে দীর্ঘতম সাবহারে কে স্বতন্ত্র উপাদানগুলির বেশি না রয়েছে তা সন্ধান করতে

import java.util.*;

class longestSubArray
{
    public static void getLongestSub(int arr[], int n, int k)
    {
        int[] count = new int[7];
        int start = 0, end = 0, curr = 0, left = 0;
        for (int i = 0; i < n; i++)
        {
            count[arr[i]]++;
            if (count[arr[i]] == 1)
                curr++;

            while (curr > k)
            {
                count[arr[left]]--;

                if (count[arr[left]] == 0)
                    curr--;
                left++;
            }
            if (i - left + 1 >= end - start + 1)
            {
                end = i;
                start = left;
            }
        }
        for (int i = start; i <= end; i++)
            System.out.print(arr[i]+" ");
    }
    public static void main(String args[])
    {
        int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
        int n = arr.length;
        int k = 3;
        getLongestSub(arr, n, k);
    }
}
2 1 2 0

জটিলতা বিশ্লেষণ

সময় জটিলতা

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

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

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