K سب سے زیادہ الگ عناصر کے ساتھ زیادہ سے زیادہ طویل عرصے سے subarray نہیں ہے


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون درگ دہلی فیس بک مائیکروسافٹ سیمسنگ Yandex
لڑی ہیش سلائیڈنگ ونڈو

مسئلہ “سب سے طویل سبریری سے K کے الگ الگ عناصر سے زیادہ نہ ہونا” بتاتا ہے کہ فرض کریں کہ آپ کے پاس صف of اشارے، مسئلے کے بیان میں سب سے طویل ذیلی صف معلوم کرنے کے لئے کہا گیا ہے جس میں مختلف عناصر سے زیادہ نہ ہونا ہے۔

مثال کے طور پرK سب سے زیادہ الگ عناصر کے ساتھ زیادہ سے زیادہ طویل عرصے سے subarray نہیں ہے

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

وضاحت

سب سے طویل ذیلی سرخی (2 ، 1 ، 2 ، 0) k کے مختلف عناصر کے ساتھ

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

وضاحت

سب سے طویل ذیلی سرخی (3 ، 4) کے مختلف عناصر کے ساتھ

الگورتھم

  1. ہر عنصر کی گنتی میں اضافہ اور رکھیں
  2. 0 سے شروع کرتے ہوئے مختلف عناصر کی گنتی برقرار رکھیں یہاں تک کہ یہ k سے زیادہ ہوجائے۔
  3. اگر گنتی k سے زیادہ ہوجائے تو ، عناصر کی گنتی کو کم کرنا شروع کریں (نقطہ آغاز)
  4. گنتی کو ہٹاتے رہیں جب تک کہ ہمارے پاس دوبارہ K فرق نہ آجائے اور ذیلی صف کے نقطہ اغاز میں بھی اضافہ ہوجائے۔
  5. سب سے طویل ذیلی اری لمبائی کی جانچ کرکے سرنی عنصر انڈیکس کے مطابق اختتام کو تازہ ترین بنائیں۔
  6. اختتامی نقطہ پر شروع ہو کر سرنی فارم پرنٹ کریں۔

وضاحت

ہم نے ایک عدد اشارے فراہم کیے ہیں ، ہم نے ایک صف میں موجود سب سے طویل ذیلی سرے تلاش کرنے کے لئے کہا ہے جس میں k کے الگ الگ عناصر سے زیادہ نہیں ہے۔ ہم اسی طرح کا طریقہ استعمال کرنے جارہے ہیں ہیشنگ. ہمیں ہر عنصر کی گنتی میں اضافہ کرتے رہنا ہے ، حالانکہ ہمیں سب سے طویل ذیلی صف تلاش کرنے کی ضرورت ہے۔ لہذا ہمیں ذیلی صف کے نقطہ اغاز اور سب ایری کے اختتامی نقطہ پر نگاہ رکھنا ہوگی۔ لہذا ، ہم اس ذیلی سرے کو شروع سے اختتام پرنٹ کریں گے جو ہمیں دیئے گئے k کے الگ الگ عناصر سے زیادہ نہیں۔

ہمیں اس چیز کی گنتی بھی برقرار رکھنی ہوگی جس سے یہ یقینی بنتا ہے کہ کوئی تعداد k سے زیادہ نہیں ہونی چاہئے۔ آئیے ہم ایک مثال پیش کرتے ہیں:

ارر [] = {4، 3، 5، 2، 1، 2، 0، 4، 5}، k = 3

ہم صف کے ہر عنصر کو چنتے ہیں اور ایک صف عنصر کی گنتی میں اضافہ کرتے ہیں اور ہر بار جب ہم چیک کرتے ہیں کہ آیا اس کا واقعہ پہلی بار ہوا ہے تو ، ہم موجودہ گنتی میں اضافہ کریں گے ، ہم اس کا موازنہ K سے کریں گے ، ہم ایسا نہیں کر رہے ہیں۔ کچھ بھی جب تک کہ یہ k سے بڑا نہ ہوجائے۔ اگر ایک بار یہ k سے زیادہ ہوجائے تو ، ہم 0 سے شروع ہونے والے عنصر کی گنتی کو کم کردیں گے ، اور قدر میں اضافہ کریں گے تاکہ اگلی بار ہم اگلے عنصر کی گنتی کو کم کرسکیں۔ ہمیں بائیں کی قیمت میں اضافہ کرنا چاہئے ، یہ ذیلی صف کا نقطہ آغاز ہوگا جب تک کہ ہمیں دوبارہ الگ الگ عناصر نہ ملے۔

اگر ہم کسی صف سے 4 ، 3 اور 5 پر غور کرتے ہیں تو ہمارے پاس i = 2 ، کرر = 3 ہیں ، اگر ہم اگلے عنصر کے لئے جائیں تو ہمیں کرر 4 ملتا ہے اور ہمیں 2 کو ذیلی صف کے نقطہ آغاز کے طور پر ملتا ہے اور ہمیں اپنے پاس رکھنا چاہئے اس وقت تک جا رہا ہے جب تک ہمیں k سے الگ عنصر نہیں مل پائے۔

ضابطے

C ++ کوڈ جس میں سب سے طویل subarray K سے زیادہ واضح عناصر سے زیادہ نہیں ہے کو تلاش کریں

#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

سب سے طویل سبریے کو تلاش کرنے کے لئے جاوا کوڈ جس میں K سے زیادہ واضح عنصر نہیں ہیں

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) وقت میں داخل کرنے ، حذف کرنے اور تلاش کرنے کی سہولت دیتا ہے۔ اس طرح وقت کی پیچیدگی لکیری ہے۔

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ بدترین صورتحال میں ، ہمیں تمام عناصر کو ذخیرہ کرنا پڑسکتا ہے۔ اس طرح خلائی پیچیدگی بھی لکیری ہوتی ہے۔