K വ്യതിരിക്തമായ നമ്പറുകളുള്ള ഏറ്റവും ചെറിയ സബ്‌റേ


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഗൂഗിൾ
അറേ ഹാഷ് സ്ലൈഡിംഗ് വിൻഡോ രണ്ട് പോയിന്റർ

നിങ്ങൾക്ക് ഒരു സംഖ്യ ഉണ്ടെന്ന് കരുതുക ശ്രേണി k എന്ന സംഖ്യയും. ശ്രേണിയിലെ ഏറ്റവും ചെറിയ ഉപ-ശ്രേണി (l, r) ഉൾക്കൊള്ളാൻ പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു, അത്തരത്തിൽ ആ ചെറിയ ഉപ-അറേയിൽ കൃത്യമായി k വ്യതിരിക്ത സംഖ്യകളുണ്ട്.

ഉദാഹരണം

ഇൻപുട്ട്:

{1, 2, 2, 3, 4, 5, 5}

k = 3

ഔട്ട്പുട്ട്:

2, 4

വിശദീകരണം:

From 2, 3, 4 2 ആണ് XNUMX മുതൽ ആരംഭിക്കുന്ന ഏറ്റവും ചെറിയ ഉപ-അറേnd സൂചിക 4 ലേക്ക്th k ഉള്ള സൂചിക, അതായത് 3 വ്യത്യസ്ത ഘടകങ്ങൾ.

ഇൻപുട്ട്:

{2, 5, 6, 7}

k = 2

ഔട്ട്പുട്ട്:

2, 3

വിശദീകരണം:

രണ്ടാം സൂചിക മുതൽ മൂന്നാം സൂചിക വരെ ആരംഭിക്കുന്ന ഏറ്റവും ചെറിയ ഉപ-അറേ {2, 5 k ആണ്, അതായത് 2 വ്യത്യസ്ത ഘടകങ്ങൾ.

അൽഗോരിതം

  1. വ്യതിരിക്തമായ ഘടകം 0 ആയും ഇടത് വശത്തും വലതുവശത്തുള്ള പോയിന്ററുകളും -1 ആയും സജ്ജമാക്കുക.
  2. അറേയിലൂടെ സഞ്ചരിക്കുക,
  3. തന്നിരിക്കുന്ന സംഖ്യയെക്കാൾ വ്യതിരിക്തമായ ഘടകങ്ങളൊന്നും കുറവല്ലെങ്കിൽ വലതുവശത്ത് 1 വർദ്ധിപ്പിക്കുക,
  4. തുടർന്ന് എണ്ണം വർദ്ധിപ്പിച്ച് അറേ ഘടകത്തിന്റെ ആവൃത്തി സംഭരിക്കുക ഭൂപടം.
  5. വ്യത്യസ്‌ത ഘടകങ്ങൾ‌ തന്നിരിക്കുന്ന സംഖ്യയ്‌ക്ക് തുല്യമാണെങ്കിൽ‌, അങ്ങനെ രൂപപ്പെടുത്തിയ നീളം മുമ്പ്‌ അപ്‌ഡേറ്റുചെയ്‌ത നീളത്തേക്കാൾ‌ ചെറുതാണെങ്കിൽ‌, ഇടത്, വലത് വശത്തെ പോയിൻററുകൾ‌ തകർക്കുക.
  6. വ്യതിരിക്തമായ മൂലകങ്ങളുടെ എണ്ണം k നേക്കാൾ കുറവാണെന്ന് കണ്ടെത്തിയാൽ തകർക്കുക.
  7. K ന് തുല്യമാണെന്ന് കണ്ടെത്തിയ വ്യത്യസ്ത ഘടകങ്ങളുടെ എണ്ണം പരിശോധിക്കുക, തുടർന്ന് വലതുവശത്തെ പോയിന്ററുകൾ വർദ്ധിപ്പിക്കുക.
  8. വ്യത്യസ്‌ത ഘടകങ്ങൾ‌ തന്നിരിക്കുന്ന സംഖ്യയ്‌ക്ക് തുല്യമാണെങ്കിൽ‌, അങ്ങനെ രൂപപ്പെടുത്തിയ നീളം മുമ്പ്‌ അപ്‌ഡേറ്റുചെയ്‌ത നീളത്തേക്കാൾ‌ ചെറുതാണെങ്കിൽ‌, ഇടത്, വലത് വശത്തെ പോയിൻററുകൾ‌ തകർക്കുക.
  9. മൂലകത്തിന്റെ ആവൃത്തി 1 ആണെന്ന് കണ്ടെത്തി, മാപ്പിൽ നിന്ന് ആ ഘടകം നീക്കംചെയ്യുക, അല്ലാത്തപക്ഷം ആ മൂലകത്തിന്റെ ആവൃത്തിയുടെ എണ്ണം കുറയ്‌ക്കുക
  10. ഇടത് വശത്തെ പോയിന്റർ 0 ഉം വലതുവശത്ത് n ന് തുല്യവുമാണെന്ന് കണ്ടെത്തിയാൽ, അത് അസാധുവാണ് എന്നാണ് ഇതിനർത്ഥം.
  11. അല്ലെങ്കിൽ, ഇടത് വശവും വലതുവശത്തെ മൂല്യങ്ങളും അച്ചടിക്കുക.

വിശദീകരണം

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

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

അറേയുടെ സഞ്ചാരത്തിനുശേഷം, ഇടത് വശത്തെ പോയിന്റർ 0 ഉം വലതുവശത്തെ പോയിന്റർ n ഉം ആണെന്ന് കണ്ടെത്തിയാൽ, അത് അസാധുവായ കെ ആണെന്ന് അർത്ഥമാക്കുന്നു. ഇടത്, വലത് വശത്തെ പോയിന്ററിന്റെ മൂല്യം അച്ചടിക്കുക, അത് ചെറിയ ഉപ-അറേയുടെ ആരംഭ പോയിന്റും അവസാന പോയിന്റും ഉൾക്കൊള്ളുന്നു.

നടപ്പിലാക്കൽ

K വ്യതിരിക്ത സംഖ്യകളുള്ള ഏറ്റവും ചെറിയ സബ്‌റേയ്‌ക്കുള്ള C ++ പ്രോഗ്രാം # ഉൾപ്പെടുന്നു

#include<map>

using namespace std;

void getSmallestSubarray(int arr[], int n, int k)
{
    int left = 0, right = n;
    int j = -1;
    map<int, int> MAP;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            j++;
            if (MAP.size() < k)
                MAP[arr[j]]++;

            if (MAP.size() == k && ((right - left) >= (j - i)))
            {
                left = i;
                right = j;
                break;
            }

        }
        if (MAP.size() < k)
            break;

        while (MAP.size() == k)
        {
            if (MAP[arr[i]] == 1)
                MAP.erase(arr[i]);
            else
                MAP[arr[i]]--;

            i++;

            if (MAP.size() == k && (right - left) >= (j - i))
            {
                left = i;
                right = j;
            }
        }
        if (MAP[arr[i]] == 1)
            MAP.erase(arr[i]);
        else
            MAP[arr[i]]--;
    }
    if (left == 0 && right == n)
        cout << "Invalid k" << endl;
    else
        cout << left << " " << right;
}
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getSmallestSubarray(arr, n, k);
    return 0;
}
2 4

K വ്യതിരിക്ത നമ്പറുകളുള്ള ഏറ്റവും ചെറിയ സബാരേയ്ക്കുള്ള ജാവ പ്രോഗ്രാം

import java.util.HashMap;
import java.util.Map;
class smallestSubArray
{
    public static void getSmallestSubarray(int arr[], int n, int k)
    {
        int left = 0, right = n;
        int j = -1;
        HashMap<Integer, Integer> MAP=new HashMap<>();
        for (int i=0; i<n; i++)
        {
            while (j < n-1)
            {
                j++;
                if (MAP.size() < k)
                {

                    if(MAP.containsKey( arr[j] ))
                        MAP.put( arr[j], MAP.get( arr[j] ) + 1 );
                    else
                        MAP.put(arr[j],1);
                }

                if (MAP.size() == k && ((right - left) >= (j - i)))
                {
                    left = i;
                    right = j;
                    break;
                }
            }
            if (MAP.size() < k)
                break;

            while (MAP.size() == k)
            {
                if (MAP.get(arr[i]) == 1)
                    MAP.remove(arr[i]);
                else
                    MAP.put(arr[i], MAP.get(arr[i])-1);

                i++;

                if (MAP.size() == k && (right - left) >= (j - i))
                {
                    left = i;
                    right = j;
                }
            }
            if (MAP.get(arr[i]) == 1)
                MAP.remove(arr[i]);
            else
                MAP.put(arr[i], MAP.get(arr[i])-1);
        }
        if (left == 0 && right == n)
            System.out.println("Invalid k");
        else
            System.out.println(left+" "+right);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 5, 5};
        int n = arr.length;
        int k = 3;
        getSmallestSubarray(arr, n, k);

    }
}
2 4

K വ്യതിരിക്തമായ നമ്പറുകളുള്ള ഏറ്റവും ചെറിയ സബ്‌റേയ്‌ക്കുള്ള സങ്കീർണ്ണത വിശകലനം

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

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

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

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.