सबसे लंबे समय तक सबरे के पास K से अलग तत्व नहीं होते हैं


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना गढ़ Delhivery Facebook माइक्रोसॉफ्ट सैमसंग Yandex
ऐरे हैश फिसलने वाली खिडकी

समस्या "सबसे लंबे समय तक उपश्रेण कश्मीर तत्वों से अधिक नहीं है" बताता है कि आपके पास एक है सरणी 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) k अलग तत्वों के साथ

कलन विधि

  1. प्रत्येक तत्व की गिनती बढ़ाएँ और रखें
  2. 0 से शुरू करके अलग-अलग तत्वों की गिनती बनाए रखें जब तक कि यह k से अधिक न हो जाए।
  3. यदि गणना k से अधिक हो जाती है, तो तत्वों की गिनती (प्रारंभिक बिंदु) को कम करना शुरू करें।
  4. गणना को तब तक हटाते रहें जब तक कि हमें फिर से कश्मीर न मिल जाए अलग-अलग तत्व उप-सरणी के शुरुआती बिंदु को भी बढ़ाते हैं।
  5. सबसे लंबे उप-सरणी की लंबाई की जाँच करके सरणी तत्व सूचकांक के अनुसार अंत को अपडेट करें।
  6. एंड-पॉइंट से शुरू होने वाले सरणी फॉर्म को प्रिंट करें।

व्याख्या

हमने एक पूर्णांक दिया है, हमने एक सरणी में मौजूद सबसे लंबे उप-सरणी का पता लगाने के लिए कहा है जो कि अलग-अलग तत्वों से अधिक नहीं है। हम एक समान विधि का उपयोग करने जा रहे हैं हैशिंग। हमें प्रत्येक तत्व की गिनती को बढ़ाते रहना है, हालांकि हमें सबसे लंबे उप-सरणी को खोजने की आवश्यकता है। इसलिए हमें उप-सरणी के शुरुआती बिंदु और उप-सरणी के अंतिम बिंदु पर नजर बनाए रखना होगा। इसलिए, हम उस उप-सरणी को शुरू से अंत तक कश्मीर तत्वों से अधिक नहीं के साथ देंगे, जो हमें दिया गया है।

हमें उस चीज़ की गिनती भी बनाए रखनी होगी जो यह सुनिश्चित करती है कि कोई भी संख्या k से अधिक न हो। एक उदाहरण लेते हैं:

अर्र [] = {४, ३, ५, २, १, २, ०, ४, ५}, के = ३

हम सरणी के प्रत्येक तत्व को लेते हैं और एक सरणी तत्व की गिनती बढ़ाते हैं और हर बार जब हम जांचते हैं कि क्या इसकी घटना पहली बार है, तो हम वर्तमान संख्या में वृद्धि करेंगे, हम इसकी तुलना k से करने जा रहे हैं, हम ऐसा नहीं कर रहे हैं कुछ भी जब तक यह k से बड़ा नहीं हो जाता। यदि एक बार यह k से अधिक हो जाता है, तो हम 0 से शुरू होने वाले तत्व की गिनती को कम कर देंगे, और मूल्य में वृद्धि करेंगे ताकि अगली बार हम अगले तत्व की गिनती को कम कर सकें। हमें बाईं ओर का मान बढ़ाना चाहिए, यह उप-सरणी का शुरुआती बिंदु होगा जब तक कि हम फिर से अलग-अलग तत्व नहीं मिला।

यदि हम एक सरणी से 4, 3 और 5 पर विचार करते हैं, तो हमारे पास i = 2, वक्र = 3 है, यदि हम अगले तत्व के लिए जाते हैं, तो हमें वक्र मिलता है 4 के रूप में हम 2 को उप-सरणी के शुरुआती बिंदु के रूप में प्राप्त करते हैं और हमें रखना चाहिए जब तक हम कश्मीर को अलग-अलग तत्वों से अधिक नहीं मिला।

कोड

C ++ कोड 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

जावा कोड सबसे लंबे समय तक सबर्रे को खोजने के लिए के से अधिक अलग तत्व नहीं है

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

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। हैशमैप का उपयोग करके हम ओ (1) समय में सम्मिलित, हटा और खोज सकते हैं। इस प्रकार समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। सबसे खराब स्थिति में, हमें सभी तत्वों को संग्रहीत करना पड़ सकता है। इस प्रकार अंतरिक्ष की जटिलता भी रैखिक है।