K-ээс ихгүй ялгаатай элемент бүхий хамгийн урт дэд хэсэг


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Citadel Дели Facebook-ийн Microsoft- Samsung Yandex
Array Хаш Гулгадаг цонх

"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

Тайлбар

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-ээс эхлэн бууруулж, утгыг нэмэгдүүлснээр дараагийн удаа дараагийн элементийн тоог бууруулж болно. Бид зүүн талын утгыг нэмэгдүүлэх ёстой бөгөөд энэ нь ялгаатай элементүүдийг дахин олтол дэд массивын эхлэх цэг байх болно.

Хэрэв массиваас 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-ээс олон ялгаатай элемент агуулаагүй хамгийн урт дэд мөрийг олох Java код

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" нь массив дахь элементүүдийн тоо юм. Хамгийн муу тохиолдолд бид бүх элементүүдийг хадгалах хэрэгтэй болж магадгүй юм. Тиймээс сансрын нарийн төвөгтэй байдал нь мөн шугаман юм.