K ට වඩා වැඩි මූලද්‍රව්‍ය නොමැති දීර් est තම උපසිරැසි


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් සිටඩෙල් දිල්ලි ෆේස්බුක් මයික්රොසොෆ්ට් Samsung ජංගම දුරකථන Yandex
අරා හැෂ් ස්ලයිඩින් කවුළුව

“K ට වඩා වැඩි මූලද්‍රව්‍යයක් නොමැති දීර් est තම උපසිරැසි” ගැටළුවෙහි දැක්වෙන්නේ ඔබට එය ඇතැයි සිතමු අරාව of නිඛිල, k විවිධ මූලද්‍රව්‍යයන්ට වඩා වැඩි නොවන දීර් est තම උප-අරාව සොයා ගැනීමට ගැටළු ප්‍රකාශය ඉල්ලා සිටී.

උදාහරණයක්K ට වඩා වැඩි මූලද්‍රව්‍ය නොමැති දීර් est තම උපසිරැසි

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 ට වඩා වැඩි මූලද්‍රව්‍යයන් නොමැති අරාවක ඇති දීර් est තම උප-අරාව සොයා ගැනීමට අපි ඉල්ලා සිටිමු. අපි ඒ හා සමාන ක්‍රමයක් භාවිතා කරන්නෙමු හැෂිං. අපට දිගම උප-අරාව සොයා ගැනීමට අවශ්‍ය වුවද, එක් එක් මූලද්‍රව්‍යයන්ගේ ගණන වැඩි කරමින් සිටිය යුතුය. එබැවින් උප-අරාවෙහි ආරම්භක ස්ථානය සහ උප අරාවෙහි අවසාන ලක්ෂ්‍යය පිළිබඳව අප විමසිල්ලෙන් සිටිය යුතුය. එබැවින්, අපට ලබා දී ඇති 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 ට වඩා වැඩි මූලද්‍රව්‍ය සොයා ගන්නා තෙක්.

කේතය

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) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. හැෂ්මැප් භාවිතා කිරීමෙන් O (1) වේලාව තුළ ඇතුළත් කිරීමට, මකා දැමීමට සහ සෙවීමට අපට ඉඩ ලබා දේ. මේ අනුව කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. නරකම අවස්ථාවක, අපට සියලු අංග ගබඩා කිරීමට සිදුවනු ඇත. මේ අනුව අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.