subarray ທີ່ຍາວທີ່ສຸດບໍ່ມີຫຼາຍກ່ວາອົງປະກອບທີ່ແຕກຕ່າງກັນ K


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon Citadel ເດລີ ເຟສບຸກ Microsoft Samsung Yandex
Array Hash ແຖບເລື່ອນ

ປັນຫາ“ ອະວະກາດທີ່ຍາວທີ່ສຸດບໍ່ມີຫຼາຍກ່ວາອົງປະກອບທີ່ແຕກຕ່າງກັນ K” ລະບຸວ່າເຈົ້າມີ array of integers, ຄຳ ຖະແຫຼງທີ່ມີບັນຫາຂໍໃຫ້ຄົ້ນຫາອະນຸສັນຍາຍ່ອຍທີ່ຍາວທີ່ສຸດທີ່ບໍ່ມີຂະ ໜາດ ໃຫຍ່ກ່ວາອົງປະກອບ 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. ຮັກສາການນັບ ຈຳ ນວນດັ່ງກ່າວຈົນກວ່າພວກເຮົາຈະໄດ້ພົບກັບອົງປະກອບທີ່ແຕກຕ່າງກັນຕື່ມອີກກໍ່ເຮັດໃຫ້ຈຸດເລີ່ມຕົ້ນຂອງແຖວຍ່ອຍ.
  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 ເປັນຈຸດເລີ່ມຕົ້ນຂອງ sub-array ແລະພວກເຮົາຄວນເກັບ ໄປຈົນກ່ວາພວກເຮົາພົບເຫັນຫຼາຍກ່ວາອົງປະກອບທີ່ແຕກຕ່າງກັນ 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 ເພື່ອຊອກຫາ 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" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ການໃຊ້ hashmap ຊ່ວຍໃຫ້ພວກເຮົາແຊກ, ລຶບ, ແລະຄົ້ນຫາໃນເວລາ O (1). ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ, ພວກເຮົາອາດຈະຕ້ອງເກັບຮັກສາອົງປະກອບທັງ ໝົດ ໄວ້. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ຍັງເປັນເສັ້ນ.