subarray វែងបំផុតមិនមានច្រើនជាង K ដែលខុសគ្នា


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon Citadel ដេលីវ៉ាយ Facebook ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Samsung Yandex
អារេ ហាស់ រអិលបង្អួច

បញ្ហា“ នាវាមុជទឹកដែលវែងជាងគេមិនមានធាតុ K ខុសគ្នាទេ” បញ្ជាក់ថាអ្នកមាន អារេ of ចំនួនគត់សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យស្វែងរកអារេរងវែងបំផុតដែលមិនធំជាង k ធាតុខុសគ្នា។

ឧទាហរណ៍subarray វែងបំផុតមិនមានច្រើនជាង K ដែលខុសគ្នា

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

ការពន្យល់

អារេរងវែងបំផុត (២, ១, ២, ០) ដែលមានធាតុ k ខុសគ្នា

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

ការពន្យល់

អារេរងវែងបំផុត (៣, ៤) ដែលមានធាតុ k ខុសគ្នា

ក្បួនដោះស្រាយ

  1. បង្កើននិងរក្សាចំនួនធាតុនីមួយៗ
  2. ចាប់ផ្តើមពី ០ រក្សាចំនួននៃធាតុខុសគ្នារហូតដល់វាធំជាង k ។
  3. ប្រសិនបើការរាប់ធំជាង k ចាប់ផ្តើមបន្ថយចំនួនធាតុ (ចំណុចចាប់ផ្តើម) ។
  4. បន្តយកចំនួនចេញរហូតទាល់តែយើងទទួលបានធាតុ k ខុសគ្នាម្តងទៀតបង្កើនចំណុចចាប់ផ្តើមនៃអារេរង។
  5. ធ្វើបច្ចុប្បន្នភាពចុងបញ្ចប់ដោយយោងតាមសន្ទស្សន៍ធាតុអារេដោយពិនិត្យមើលប្រវែងអនុជួរវែងបំផុត។
  6. បោះពុម្ពសំណុំបែបបទអារេចាប់ផ្តើមចំណុចបញ្ចប់។

ការពន្យល់

យើងបានអោយចំនួនគត់នៃចំនួនគត់យើងបានស្នើអោយរកឃើញអនុជួរវែងបំផុតដែលមាននៅក្នុងអារេមួយដែលមានមិនលើសពី k ធាតុខុសគ្នា។ យើងនឹងប្រើវិធីសាស្ត្រស្រដៀងគ្នា ហាន់។ យើងត្រូវបន្តបង្កើនចំនួនធាតុនីមួយៗទោះបីយើងត្រូវរកអារេវែងបំផុតក៏ដោយ។ ដូច្នេះយើងត្រូវរក្សាភ្នែកលើចំណុចចាប់ផ្តើមនៃអនុជួរនិងនៅចុងបញ្ចប់នៃអារេរង។ ដូច្នេះយើងនឹងបោះពុម្ពអារេរងនោះពីចំនុចចាប់ផ្តើមដល់ទីបញ្ចប់ដោយមិនមានច្រើនជាង k ធាតុខុសគ្នាដែលបានផ្តល់ឱ្យយើងទេ។

យើងក៏ត្រូវរក្សាចំនួននៃវត្ថុដែលធ្វើឱ្យប្រាកដថាមិនមានលេខមិនលើសពី k ។ តោះយើងយកឧទាហរណ៍៖

មកដល់ [] = {៤, ៣, ៥, ២, ១, ២, ០, ៤, ៥}, k = ៣

យើងជ្រើសរើសធាតុនីមួយៗនៃអារេនិងបង្កើនចំនួនធាតុអារេហើយរាល់ពេលដែលយើងពិនិត្យមើលថាតើការកើតឡើងរបស់វាជាលើកដំបូងយើងនឹងបង្កើនចំនួនបច្ចុប្បន្នយើងនឹងប្រៀបធៀបវាជាមួយ k យើងមិនធ្វើទេ អ្វីទាំងអស់រហូតដល់វាធំជាង k ។ ប្រសិនបើនៅពេលដែលវាធំជាង k យើងនឹងបន្ថយចំនួនធាតុដែលចាប់ផ្តើមពីលេខ 0 ហើយធ្វើឱ្យតំលៃកើនឡើងដូច្នេះពេលក្រោយយើងអាចបន្ថយចំនួនធាតុបន្ទាប់។ យើងគួរតែបង្កើនតម្លៃនៅខាងឆ្វេងវានឹងក្លាយជាចំណុចចាប់ផ្តើមនៃអនុជួររហូតដល់យើងរកឃើញធាតុ k ខុសគ្នាម្តងទៀត។

ប្រសិនបើយើងពិចារណា ៤, ៣ និង ៥ ពីអារេយើងមាន i = ២, curr = ៣ ប្រសិនបើយើងទៅរកធាតុបន្ទាប់យើងទទួលបាន curr ដូច ៤ យើងទទួលបាន ២ ជាចំណុចចាប់ផ្តើមនៃអនុជួរហើយយើងគួររក្សាទុក ទៅរហូតទាល់តែយើងរកឃើញធាតុខុសគ្នាច្រើនជាង 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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ការប្រើប្រាស់ហាសអនុញ្ញាតឱ្យយើងបញ្ចូលលុបនិងស្វែងរកក្នុងរយៈពេលអូ (១) ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ក្នុងករណីដ៏អាក្រក់បំផុតយើងប្រហែលជាត្រូវរក្សាទុកធាតុទាំងអស់។ ដូច្នេះភាពស្មុគស្មាញនៃលំហរក៏ជាលីនេអ៊ែរដែរ។