طولانی ترین زیرشیروانی که بیش از K عناصر مشخص ندارد  


سطح دشواری متوسط
اغلب در آمازون دژ تحویل کالا فیس بوک مایکروسافت سامسونگ Yandex
صف مخلوط پنجره کشویی

مسئله "طولانی ترین زیرشیروانی که بیش از K عنصر مجزا ندارد" بیان می کند که شما فرض می کنید صف of عدد صحیح، بیانیه مسئله می خواهد طولانی ترین زیر آرایه را پیدا کند که بیش از k عناصر مختلف ندارد.

مثالطولانی ترین زیرشیروانی که بیش از K عناصر مشخص نداردسنجاق  

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

توضیح

طولانی ترین زیر آرایه (2 ، 1 ، 2 ، 0) با k عناصر مشخص

arr[] = {1, 2, 3, 4}
k=2
3, 4

توضیح

طولانی ترین زیر آرایه (3 ، 4) با k عناصر مشخص

الگوریتم  

  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 را پیدا کنیم.

رمز  

کد C ++ برای پیدا کردن طولانی ترین زیرآرایه که بیش از 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

تحلیل پیچیدگی  

پیچیدگی زمان

O (N) جایی که "n" تعداد عناصر آرایه است. استفاده از hashmap به ما امکان می دهد تا در زمان O (1) درج ، حذف و جستجو کنیم. بنابراین پیچیدگی زمان خطی است.

همچنین مشاهده کنید
حداقل تعداد عناصر را حذف کنید به طوری که هیچ عنصر مشترکی در هر دو آرایه وجود نداشته باشد

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است. در بدترین حالت ، ممکن است مجبور شویم همه عناصر را ذخیره کنیم. بنابراین پیچیدگی فضا نیز خطی است.