subarray ที่ยาวที่สุดที่ไม่มีองค์ประกอบที่แตกต่างกันมากกว่า K  


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน ป้อมปราการ เดลี Facebook ไมโครซอฟท์ ซัมซุง Yandex
แถว กัญชา หน้าต่างบานเลื่อน

ปัญหา“ subarray ที่ยาวที่สุดที่ไม่มีองค์ประกอบที่แตกต่างกันมากกว่า K” ระบุว่าสมมติว่าคุณมีไฟล์ แถว of จำนวนเต็มคำสั่งปัญหาจะขอให้ค้นหาอาร์เรย์ย่อยที่ยาวที่สุดที่มีองค์ประกอบต่างกันไม่เกิน k

ตัวอย่างsubarray ที่ยาวที่สุดที่ไม่มีองค์ประกอบที่แตกต่างกันมากกว่า 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 เราจะใช้วิธีการที่คล้ายกันเช่น hashing. เราต้องเพิ่มจำนวนของแต่ละองค์ประกอบไปเรื่อย ๆ แม้ว่าเราจะต้องหาอาร์เรย์ย่อยที่ยาวที่สุด ดังนั้นเราต้องจับตาดูจุดเริ่มต้นของอาร์เรย์ย่อยและที่จุดสิ้นสุดของอาร์เรย์ย่อย ดังนั้นเราจะพิมพ์อาร์เรย์ย่อยนั้นตั้งแต่ต้นจนจบโดยมีองค์ประกอบที่แตกต่างกันไม่เกิน 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

รหัส  

รหัส C ++ เพื่อค้นหา subarray ที่ยาวที่สุดที่ไม่มีองค์ประกอบที่แตกต่างกันมากกว่า 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 เพื่อค้นหา subarray ที่ยาวที่สุดที่ไม่มีองค์ประกอบที่แตกต่างกันมากกว่า 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” คือจำนวนองค์ประกอบในอาร์เรย์ การใช้แฮชแมปช่วยให้เราสามารถแทรกลบและค้นหาในเวลา O (1) ได้ ดังนั้นความซับซ้อนของเวลาจึงเป็นเชิงเส้น

ดูสิ่งนี้ด้วย
ลบจำนวนองค์ประกอบขั้นต่ำที่ไม่มีองค์ประกอบทั่วไปอยู่ในทั้งสองอาร์เรย์

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ ในกรณีที่เลวร้ายที่สุดเราอาจต้องจัดเก็บองค์ประกอบทั้งหมด ดังนั้นความซับซ้อนของพื้นที่จึงเป็นเส้นตรงด้วย