K க்கும் மேற்பட்ட தனித்துவமான கூறுகளைக் கொண்டிருக்காத மிக நீளமான சப்ரே


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் சிட்டாடல் Delhivery பேஸ்புக் மைக்ரோசாப்ட் சாம்சங் யாண்டேக்ஸ்
அணி ஹாஷ் நெகிழ் சாளரம்

“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

விளக்கம்

கே தனித்துவமான கூறுகளைக் கொண்ட மிக நீளமான துணை வரிசை (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, curr = 3, அடுத்த உறுப்புக்குச் சென்றால், நாம் கர்ரை 4 ஆகப் பெறுகிறோம், 2 ஐ துணை வரிசையின் தொடக்க புள்ளியாகப் பெறுகிறோம், நாம் வைத்திருக்க வேண்டும் 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. ஹாஷ்மாப்பைப் பயன்படுத்துவது O (1) நேரத்தில் செருக, நீக்க மற்றும் தேட அனுமதிக்கிறது. இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. மோசமான நிலையில், நாம் எல்லா உறுப்புகளையும் சேமிக்க வேண்டியிருக்கும். இதனால் விண்வெளி சிக்கலானது நேரியல் ஆகும்.