K కంటే ఎక్కువ విభిన్న అంశాలను కలిగి లేని పొడవైన సబ్రే


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ సిటాడెల్ Delhivery <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> మైక్రోసాఫ్ట్ శామ్సంగ్ Yandex
అర్రే హాష్ స్లైడింగ్ విండో

“పొడవైన సబ్‌రేలో K కంటే ఎక్కువ విభిన్న అంశాలు లేవు” అనే సమస్య మీకు ఉందని అనుకుందాం అమరిక of పూర్ణాంకాల, సమస్య స్టేట్మెంట్ k వేర్వేరు అంశాల కంటే ఎక్కువ లేని పొడవైన ఉప-శ్రేణిని తెలుసుకోవడానికి అడుగుతుంది.

ఉదాహరణK కంటే ఎక్కువ విభిన్న అంశాలను కలిగి లేని పొడవైన సబ్రే

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

వివరణ

K విభిన్న అంశాలతో పొడవైన ఉప-శ్రేణి (2, 1, 2, 0)

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

వివరణ

K విభిన్న అంశాలతో పొడవైన ఉప-శ్రేణి (3, 4)

అల్గారిథం

  1. ప్రతి మూలకం యొక్క సంఖ్యను పెంచండి మరియు ఉంచండి
  2. 0 నుండి మొదలుకొని k కంటే ఎక్కువ అయ్యే వరకు విభిన్న మూలకాల సంఖ్యను నిర్వహించండి.
  3. కౌంట్ k కంటే ఎక్కువగా ఉంటే, మూలకాల సంఖ్యను ప్రారంభించడం ప్రారంభించండి (ప్రారంభ స్థానం).
  4. మేము మళ్ళీ వచ్చేవరకు గణనను తీసివేయండి k విభిన్న అంశాలు ఉప-శ్రేణి యొక్క ప్రారంభ బిందువును కూడా పెంచుతాయి.
  5. పొడవైన ఉప-శ్రేణి పొడవును తనిఖీ చేయడం ద్వారా శ్రేణి మూలకం సూచిక ప్రకారం ముగింపును నవీకరించండి.
  6. ఎండ్ పాయింట్ నుండి ప్రారంభమయ్యే శ్రేణి ఫారమ్‌ను ప్రింట్ చేయండి.

వివరణ

మేము పూర్ణాంకాల శ్రేణిని ఇచ్చాము, k విభిన్న మూలకాల కంటే ఎక్కువ లేని శ్రేణిలో ఉన్న పొడవైన ఉప-శ్రేణిని కనుగొనమని మేము కోరాము. మేము ఇలాంటి పద్ధతిని ఉపయోగించబోతున్నాము హాషింగ్. మేము ప్రతి మూలకం యొక్క గణనను పెంచుతూనే ఉండాలి, అయినప్పటికీ మనం పొడవైన ఉప-శ్రేణిని కనుగొనవలసి ఉంది. కాబట్టి మేము ఉప-శ్రేణి యొక్క ప్రారంభ బిందువుపై మరియు ఉప-శ్రేణి యొక్క ముగింపు బిందువుపై ఒక కన్ను ఉంచాలి. కాబట్టి, ఆ ఉప-శ్రేణిని మనకు ఇచ్చిన k కంటే ఎక్కువ కాకుండా, విభిన్న అంశాలతో ముద్రించాము.

K కంటే ఎక్కువ సంఖ్య మించరాదని నిర్ధారించుకునే ఆ విషయం యొక్క గణనను కూడా మనం నిర్వహించాలి. ఒక ఉదాహరణ తీసుకుందాం:

అర్ [] = {4, 3, 5, 2, 1, 2, 0, 4, 5}, క = 3

మేము శ్రేణి యొక్క ప్రతి మూలకాన్ని ఎంచుకుంటాము మరియు శ్రేణి మూలకం యొక్క గణనను పెంచుతాము మరియు ప్రతిసారీ దాని సంభవం మొదటిసారిగా ఉందో లేదో తనిఖీ చేస్తే, మేము ప్రస్తుత గణనను పెంచుతాము, మేము దానిని k తో పోల్చబోతున్నాము, మేము చేయలేము k కంటే ఎక్కువ అయ్యే వరకు ఏదైనా. అది k కంటే ఎక్కువైతే, మేము 0 నుండి ప్రారంభమయ్యే మూలకం యొక్క సంఖ్యను తగ్గిస్తాము మరియు విలువను పెంచుతాము, తద్వారా తదుపరిసారి మనం తదుపరి మూలకం యొక్క సంఖ్యను తగ్గించవచ్చు. మేము ఎడమ విలువను పెంచాలి, k విభిన్న అంశాలను మళ్ళీ కనుగొనే వరకు ఇది ఉప-శ్రేణి యొక్క ప్రారంభ స్థానం అవుతుంది.

మేము శ్రేణి నుండి 4, 3 మరియు 5 ను పరిశీలిస్తే, మనకు i = 2, కర్ర్ = 3 ఉంది, మనం తరువాతి మూలకం కోసం వెళితే కర్ర్ 4 గా వస్తుంది, మనకు 2 ను ఉప-శ్రేణి యొక్క ప్రారంభ బిందువుగా పొందుతాము మరియు మనం ఉంచాలి k కంటే ఎక్కువ విభిన్న అంశాలను కనుగొనే వరకు వెళ్తాము.

కోడ్

పొడవైన సబ్‌రేలో K కంటే ఎక్కువ విభిన్న అంశాలు లేవని కనుగొనడానికి C ++ కోడ్

#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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. హ్యాష్‌మ్యాప్‌ను ఉపయోగించడం ద్వారా O (1) సమయంలో చొప్పించడానికి, తొలగించడానికి మరియు శోధించడానికి అనుమతిస్తుంది. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. చెత్త సందర్భంలో, మేము అన్ని అంశాలను నిల్వ చేయాల్సి ఉంటుంది. అందువలన స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది.