أطول مصفوفة فرعية لا تحتوي على أكثر من عناصر مميزة K.  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون قلعة التسليم Facebook Microsoft سامسونج ياندكس
مجموعة مزيج نافذة منزلقة

تنص مشكلة "أطول مجموعة فرعية لا تحتوي على أكثر من عناصر مميزة 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. دعونا نأخذ مثالا على ذلك:

وصول [] = {4 ، 3 ، 5 ، 2 ، 1 ، 2 ، 0 ، 4 ، 5} ، ك = 3

نختار كل عنصر من عناصر المصفوفة ونزيد عدد عنصر المصفوفة وفي كل مرة نتحقق مما إذا كان حدوثه لأول مرة ، سنزيد العدد الحالي ، وسنقارنه بـ k ، ولا نقوم بذلك أي شيء حتى يصبح أكبر من k. إذا أصبح العدد أكبر من k ، فسنقلل عدد العناصر بدءًا من 0 ، ونزيد القيمة حتى نتمكن في المرة القادمة من تقليل عدد العنصر التالي. يجب أن نزيد قيمة اليسار ، ستكون نقطة البداية للمصفوفة الفرعية حتى نعثر مرة أخرى على عناصر مميزة k.

إذا أخذنا في الاعتبار 4 و 3 و 5 من مصفوفة لدينا i = 2 ، تيار = 3 ، إذا انتقلنا إلى العنصر التالي نحصل على التيار مثل 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

كود Java للبحث عن أطول مجموعة فرعية لا تحتوي على أكثر من 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 (ن) أين "ن" هو عدد العناصر في المصفوفة. يسمح لنا استخدام hashmap بإدخال وحذف والبحث في وقت O (1). وبالتالي فإن التعقيد الزمني خطي.

انظر أيضا
قم بإزالة الحد الأدنى من عدد العناصر بحيث لا يوجد عنصر مشترك في كلتا المصفوفتين

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. في أسوأ الأحوال ، قد نضطر إلى تخزين جميع العناصر. وبالتالي فإن تعقيد الفضاء يكون خطيًا أيضًا.