ከ K የተለዩ አካላት የሉትም ረጅሙ ንዑስ ቡድን  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ግልብጥብጥ አቅርቦት ፌስቡክ የ Microsoft ሳምሰንግ Yandex
ሰልፍ ሃሽ የተንሸራታች መስኮት

ችግሩ “ረጅሙ ንዑስ ክፍል ከ K ልዩ ልዩ ንጥረ ነገሮች የሉትም” የሚለው እንዳለዎት ይናገራል ደርድር of ኢንቲጀሮች፣ የችግሩ መግለጫ ከኬ የተለያዩ አካላት ያልበለጠ ረጅሙን ንዑስ ክፍልን ለማወቅ ይጠይቃል።

ለምሳሌከ K የተለዩ አካላት የሉትም ረጅሙ ንዑስ ቡድንጭንቅላታም መያያዣ መርፌ  

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) ከ k ልዩ አካላት ጋር

አልጎሪዝም  

  1. የእያንዳንዱን ንጥረ ነገር ብዛት ይጨምሩ እና ያቆዩ
  2. ከ 0 ጀምሮ ከ k እስከሚበልጥ ድረስ የተለዩ አባላትን ቆጠራ ያቆዩ ፡፡
  3. ቆጠራው ከ k የሚበልጥ ከሆነ የንጥረ ነገሮችን ብዛት (መነሻ ነጥብ) መቀነስ ይጀምሩ ፡፡
  4. እንደገና የተለያዩ ነጥቦችን እስክናገኝ ድረስ ቆጠራውን ማራገፉን ይቀጥሉ እንዲሁም የንዑስ ድርድር መነሻ ቦታን ይጨምራሉ።
  5. ረዥሙን ንዑስ-ድርድር ርዝመትን በመፈተሽ በመድረክ አባሉ መረጃ ጠቋሚ መሠረት መጨረሻውን ያዘምኑ።
  6. ከጫፍ-ነጥብ ጀምሮ የድርድርን ቅጽ ያትሙ።

ማስረጃ

ብዙ የቁጥር ቁጥሮች ሰጠናል ፣ ከኬይ የተለዩ አባሎች ከሌሉበት እጅግ በጣም ረዥሙን ንዑስ-ድርድር ለማወቅ ጠይቀናል። እኛ እንደ አንድ ተመሳሳይ ዘዴ ልንጠቀም ነው ማሳከክ. ረዥሙን ንዑስ ድርድር መፈለግ ቢኖርብንም የእያንዳንዱን ንጥረ ነገር ብዛት መጨመር መቀጠል አለብን። ስለዚህ በንዑስ-ክፍል መነሻ እና በንዑስ-ረድፍ መጨረሻ ነጥብ ላይ ዓይንን መጠበቅ አለብን ፡፡ ስለዚህ ያንን ንዑስ ድርድር ከመጀመሪያው እስከ መጨረሻው በሰጡን በተሰጡን ከ k ልዩ ባልሆኑ አካላት እናተምበታለን ፡፡

ተመልከት
አባላትን በድግግሞሽ ደርድር

እንዲሁም ምንም ቁጥር ከኪ እንዳይበልጥ የሚያረጋግጥ የዚያን ነገር ቆጠራ መጠበቅ አለብን። እስቲ አንድ ምሳሌ እንውሰድ-

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

እያንዳንዱን የድርጅት ክፍል እንመርጣለን እና የአንድ ድርድር አባል ብዛት እንጨምራለን እናም ይህ ክስተት ለመጀመሪያ ጊዜ መሆኑን በምንመረምርበት ጊዜ ሁሉ የአሁኑን ቁጥር እንጨምራለን ፣ ከ k ጋር እናወዳድረዋለን ፣ አናደርግም ማንኛውንም ነገር ከኬ. አንዴ ከ k የበለጠ ከሆነ ፣ ከ 0 ጀምሮ የሚገኘውን ንጥረ ነገር ቁጥር እንቀንሳለን ፣ እና በሚቀጥለው ጊዜ የሚቀጥለውን ንጥረ ነገር ብዛት ለመቀነስ እንድንችል እሴቱን እንጨምርበታለን። የግራውን እሴት መጨመር አለብን ፣ እንደገና የተለያዩ ንጥረ ነገሮችን እስክናገኝ ድረስ ንዑስ-ድርድር መነሻ ነጥብ ይሆናል።

4 ፣ 3 እና 5 ን ከአንድ ድርድር ካየን i = 2 ፣ curr = 3 አለን ፣ ወደ ቀጣዩ ንጥረ ነገር ከሄድን 4 ን እናገኛለን 2 ን እናገኛለን XNUMX ን እንደ ንዑስ ድርድር መነሻ እናገኛለን እናም መጠበቅ አለብን ከካ በላይ ልዩ የሆኑትን አካላት እስክናገኝ ድረስ መሄድ ፡፡

ኮድ  

ከ C የተለዩ አካላት የሉትም ረጅሙን ንዑስ ክፍል ለማግኘት የ 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) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ሃሽፕ በመጠቀም O (1) ጊዜ ውስጥ ለማስገባት ፣ ለመሰረዝ እና ለመፈለግ ያስችለናል ፡፡ ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

ተመልከት
በሁለቱም ድርድር ውስጥ ምንም ዓይነት የጋራ ንጥረ ነገር የሌለባቸውን አነስተኛ ንጥረ ነገሮችን ብዛት ያስወግዱ

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። በጣም በከፋ ሁኔታ ውስጥ ሁሉንም ንጥረ ነገሮች ማከማቸት ሊኖርብን ይችላል ፡፡ ስለዚህ የቦታ ውስብስብነት እንዲሁ መስመራዊ ነው።