കെ വ്യതിരിക്തമായ ഘടകങ്ങളില്ലാത്ത ദൈർഘ്യമേറിയ സബ്‌റേ


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ കോട്ട ദില്ലി ഫേസ്ബുക്ക് മൈക്രോസോഫ്റ്റ് സാംസങ് യാൻഡക്സ്
അറേ ഹാഷ് സ്ലൈഡിംഗ് വിൻഡോ

“കെയിൽ കൂടുതൽ വ്യതിരിക്തമായ ഘടകങ്ങളില്ലാത്ത ഏറ്റവും ദൈർഘ്യമേറിയ സബാരേ” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു ഉണ്ടെന്ന് കരുതുക ശ്രേണി of പൂർണ്ണസംഖ്യകൾ, 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- നേക്കാൾ ഒരു സംഖ്യ കവിയാൻ പാടില്ലെന്ന് ഉറപ്പാക്കുന്ന വസ്തുവിന്റെ എണ്ണം ഞങ്ങൾ നിലനിർത്തേണ്ടതുണ്ട്. നമുക്ക് ഒരു ഉദാഹരണം എടുക്കാം:

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

ഞങ്ങൾ അറേയുടെ ഓരോ ഘടകങ്ങളും തിരഞ്ഞെടുത്ത് ഒരു അറേ എലമെന്റിന്റെ എണ്ണം കൂട്ടുന്നു, കൂടാതെ ഇത് സംഭവിക്കുന്നത് ആദ്യമായിട്ടാണോ എന്ന് പരിശോധിക്കുമ്പോഴെല്ലാം, നിലവിലെ എണ്ണം ഞങ്ങൾ വർദ്ധിപ്പിക്കും, ഞങ്ങൾ ഇത് k യുമായി താരതമ്യപ്പെടുത്താൻ പോകുന്നു, ഞങ്ങൾ അങ്ങനെ ചെയ്യുന്നില്ല അത് k നേക്കാൾ വലുതായിത്തീരുന്നതുവരെ. ഒരിക്കൽ അത് k നേക്കാൾ വലുതാകുകയാണെങ്കിൽ, 0 മുതൽ ആരംഭിക്കുന്ന മൂലകത്തിന്റെ എണ്ണം ഞങ്ങൾ കുറയ്ക്കുകയും മൂല്യം വർദ്ധിപ്പിക്കുകയും ചെയ്യും, അങ്ങനെ അടുത്ത തവണ അടുത്ത മൂലകത്തിന്റെ എണ്ണം കുറയ്‌ക്കാൻ കഴിയും. നമ്മൾ ഇടത് മൂല്യം വർദ്ധിപ്പിക്കണം, k വ്യത്യസ്ത ഘടകങ്ങൾ വീണ്ടും കണ്ടെത്തുന്നതുവരെ ഇത് ഉപ-അറേയുടെ ആരംഭ പോയിന്റായിരിക്കും.

നമുക്ക് ഒരു അറേയിൽ നിന്ന് 4, 3, 5 എന്നിവ പരിഗണിച്ചാൽ നമുക്ക് i = 2, curr = 3 ഉണ്ട്, അടുത്ത ഘടകത്തിനായി പോയാൽ നമുക്ക് curr 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

കെയിൽ കൂടുതൽ ഘടകങ്ങളില്ലാത്ത ദൈർഘ്യമേറിയ സബ്‌റേ കണ്ടെത്താനുള്ള ജാവ കോഡ്

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഒരു ഹാഷ്‌മാപ്പ് ഉപയോഗിക്കുന്നത് O (1) സമയത്ത് ഉൾപ്പെടുത്താനും ഇല്ലാതാക്കാനും തിരയാനും അനുവദിക്കുന്നു. അങ്ങനെ സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഏറ്റവും മോശം അവസ്ഥയിൽ, ഞങ്ങൾ എല്ലാ ഘടകങ്ങളും സംഭരിക്കേണ്ടതായി വന്നേക്കാം. അങ്ങനെ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.