Subarray ຂະ ໜາດ ນ້ອຍທີ່ສຸດທີ່ເກີດຂື້ນກັບທຸກໆເຫດການທີ່ພົບເລື້ອຍທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Citrix Coursera ຫ້ອງ OYO Qualtrics Synopsys Taxi4 ຮັບປະກັນ
Array Hash

ໃນ subarray ຂະຫນາດນ້ອຍທີ່ສຸດທີ່ມີການປະກົດຕົວທັງຫມົດຂອງບັນຫາອົງປະກອບທີ່ພົບເລື້ອຍທີ່ສຸດ, ພວກເຮົາໄດ້ໃຫ້ array. ເອົາຕົວເລກ "m" ໃນແຖວທີ່ມີຄວາມຖີ່ສູງສຸດ. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາກ່າວວ່າທ່ານຕ້ອງຊອກຄົ້ນຫາ subarray ຂະ ໜາດ ນ້ອຍທີ່ສຸດເຊິ່ງຍັງມີທັງ ໝົດ ຂອງຕົວເລກ "m" ໃນແຖວຍ່ອຍທີ່ນ້ອຍທີ່ສຸດ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ

[3, 5, 4, 5, 4]

ຜົນຜະລິດ

[5, 4, 5]

ຄໍາອະທິບາຍ

ເຊັ່ນດຽວກັນກັບໃນນີ້, ມີສອງອົງປະກອບທີ່ມີຄວາມຖີ່ດຽວກັນດັ່ງນັ້ນມັນຈະເອົາອົງປະກອບທີ່ເກີດຂື້ນມາກ່ອນແລະເຮັດໃຫ້ແຖວຍ່ອຍນ້ອຍທີ່ສຸດ.

subarray ຂະຫນາດນ້ອຍສຸດທີ່ມີອົງປະກອບເລື້ອຍໆທີ່ສຸດ

ສູດການຄິດໄລ່ ສຳ ລັບ subarray ຂະ ໜາດ ນ້ອຍທີ່ສຸດດ້ວຍອົງປະກອບທີ່ພົບເລື້ອຍທີ່ສຸດ

  1. ປະກາດສອງ HashMaps.
  2. ຕັ້ງຄ່າ maxfreq, minlen, winindex ເຖິງ 0.
  3. ໃນຂະນະທີ່ 0 <n
    1. ນັບແລະເກັບຮັກສາຄວາມຖີ່ຂອງຕົວເລກຂບວນເຂົ້າໃນແຜນທີ່ໃນທຸກໆເວລາທີ່ມີຄວາມ ໝາຍ.
    2. ກວດເບິ່ງວ່າອົງປະກອບປັດຈຸບັນມີຄວາມຖີ່ສູງກ່ວາ maxfreq, ຖ້າຖືກ, ຫຼັງຈາກນັ້ນເຮັດສິ່ງຕໍ່ໄປນີ້:
      • maxFreq = ນັບ [a [i]];
      • minlen = i - freqCount [a [i]] + 1;
      • winindex = freqCount [a [i]];
    3. ອີກຢ່າງ ໜຶ່ງ ຖ້າຄວາມຖີ່ສູງສຸດແມ່ນຄືກັນກັບຄວາມຖີ່ຂອງຄວາມຖີ່ໃນປະຈຸບັນແລະຄວາມຍາວຂອງ subarray ທີ່ຖືກສ້າງຕັ້ງຂື້ນແມ່ນຫນ້ອຍກ່ວາແຮ່, ຫຼັງຈາກນັ້ນເຮັດດັ່ງຕໍ່ໄປນີ້:
      • minlen = i - freqCount [a [i]] + 1;
      • winindex = freqCount [a [i]];
  4. ພິມຂບວນຈາກ winindex ຫາ winindex + minlen

ຄໍາອະທິບາຍສໍາລັບ subarray ຂະຫນາດນ້ອຍທີ່ສຸດທີ່ມີອົງປະກອບທີ່ພົບເລື້ອຍທີ່ສຸດ

ພວກເຮົາໄດ້ໃຫ້ ຄຳ ຖະແຫຼງທີ່ມີບັນຫາວ່າພວກເຮົາຕ້ອງໄດ້ຊອກຫາແຖວຍ່ອຍທີ່ນ້ອຍທີ່ສຸດເຊິ່ງຄວນມີທຸກໆເຫດການທີ່ເກີດຂື້ນເລື້ອຍໆ. ພວກເຮົາຈະປະກາດ maxFreq ສຳ ລັບການເກັບຮັກສາຄວາມຖີ່ສູງສຸດຂອງອົງປະກອບເປັນດັດສະນີ, “ ນ້ອຍ” ສຳ ລັບການ ກຳ ນົດຄວາມຍາວຕ່ ຳ ສຸດຂອງ sub-array, ແລະ “ winindex” ສຳ ລັບໃຕ້ດິນທີ່ນ້ອຍທີ່ສຸດ. ຖ້າພົບເຫັນອົງປະກອບເປັນຄັ້ງ ທຳ ອິດຫຼັງຈາກນັ້ນໃສ່ທັງສອງແຜນທີ່, ຖ້າມັນຊ້ ຳ ຊາກໃນແຜນທີ່ແລ້ວກໍ່ເກັບມັນໄວ້ໃນແຜນທີ່ນັບ.

ພວກເຮົາຈະເລີ່ມເກັບມ້ຽນອົງປະກອບແລະດັດຊະນີຂອງມັນໄວ້ ສຳ ລັບແຕ່ລະທິດທາງແລະເກັບມັນໄວ້ເພື່ອແຜນທີ່ແລະຫຼັງຈາກນັ້ນກວດເບິ່ງວ່າອົງປະກອບປັດຈຸບັນມີຄຸນຄ່າສູງກວ່າ “ maxfreq” ພວກເຮົາຈະປັບປຸງມູນຄ່າຂອງ maxFreq ແລະ “ ນ້ອຍ”.

ຖ້າຄວາມຖີ່ຂອງອົງປະກອບແມ່ນຄືກັນກັບ the “ maxfreq” ພວກເຮົາຈະກວດເບິ່ງຄວາມຍາວຂອງ subarray, ແລະປັບປຸງມັນ, ຖ້າເງື່ອນໄຂພໍໃຈ.

ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງ ສຳ ລັບ subarray ຂະ ໜາດ ນ້ອຍທີ່ສຸດກັບທຸກໆເຫດການທີ່ເກີດຂື້ນເລື້ອຍໆ:

ຍົກຕົວຢ່າງ

arr = {1, 2, 2, 2, 1}

i = 0 => ມາຮອດ [i] = 1

freqCount = [1: 0] ນັບ = [1: 1]

maxfreq = 1, minlen = i - freqCount [a [i]] + 1 = 1, winindex = 0

ພວກເຮົາຈະປັບປຸງ maxfreq ແລະ minlen ແລະ windex

i = 1 => ມາຮອດ [i] = 2

freqCount = [1: 0,2: 1] ນັບ = [1: 1, 2: 1], ບໍ່ມີຫຍັງຍົກເວັ້ນ

i = 2 => ມາຮອດ [i] = 2

freqCount = [1: 0,2: 1] ນັບ = [1: 0, 2: 2], ມັນອັບເດດພຽງແຕ່ນັບ.

maxfreq = 2, minlen = i - freqCount [a [i]] + 1 = 2, winindex = 1

i = 3 => ມາຮອດ [i] = 2

freqCount = [1: 0,2: 1] ນັບ = [1: 0, 2: 3], ມັນອັບເດດພຽງແຕ່ນັບ.

maxfreq = 3, minlen = i - freqCount [a [i]] + 1 = 3, winindex = 1

i = 4 => ມາຮອດ [i] = 1

freqCount = [1: 0,2: 1] ນັບ = [1: 1, 2: 3], ມັນອັບເດດພຽງແຕ່ນັບ.

maxfreq = 3, minlen = i - freqCount [a [i]] + 1 = 3, winindex = 1

ພວກເຮົາມີຄຸນຄ່າຂອງພວກເຮົາທີ່ minlen = 3 ແລະ winindex = 1

Loop ເປີດແລະມັນຈະສືບຕໍ່ຈາກ winindex ຫາ minlen + winindex ເຊັ່ນ, ຕັ້ງແຕ່ 1 ເຖິງຕ່ ຳ ກວ່າ 4

ແລະມັນຈະພິມ [2 2 2], ນັ້ນແມ່ນ ຄຳ ຕອບທີ່ຕ້ອງການຂອງພວກເຮົາ

ການປະຕິບັດສໍາລັບ subarray ຂະຫນາດນ້ອຍທີ່ສຸດທີ່ມີອົງປະກອບທີ່ພົບເລື້ອຍທີ່ສຸດ

ໂຄງການ C ++

#include <unordered_map>
#include<iostream>
using namespace std;

void frequentSubArray(int a[], int n)
{
    unordered_map<int, int> freqCount;
    unordered_map<int, int> count;

    int maxFreq = 0;
    int minlen, winindex;

    for (int i = 0; i < n; i++)
    {
        if (count[a[i]] == 0)
        {
            freqCount[a[i]] = i;
            count[a[i]] = 1;
        }
        else
            count[a[i]]++;

        if (count[a[i]] > maxFreq)
        {
            maxFreq = count[a[i]];
            minlen = i - freqCount[a[i]] + 1;
            winindex = freqCount[a[i]];
        }
        else if (count[a[i]] == maxFreq && i - freqCount[a[i]] + 1 < minlen)
        {
            minlen = i - freqCount[a[i]] + 1;
            winindex = freqCount[a[i]];
        }
    }
    for (int i = winindex; i < winindex + minlen; i++)
    {
        cout << a[i] << " ";
    }

}
int main()
{
    int A[] = { 1, 2, 2, 2, 1 };
    int n = sizeof(A) / sizeof(A[0]);
    frequentSubArray(A, n);
    return 0;
}
2 2 2

ໂຄງການ Java

import java.io.*;
import java.util.*;
class mostFrequentSubArray
{
    public static void frequentSubArray(int a[], int n)
    {
        HashMap<Integer, Integer> freqCount= new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> count= new HashMap<Integer, Integer>();
        int maxFreq = 0;

        int minlen = -1, winindex = -1;

        for (int i = 0; i < n; i++)
        {
            if (count.containsKey(a[i]))
            {
                count.put(a[i], count.get(a[i]) + 1);

            }
            else
            {
                freqCount.put(a[i], i) ;
                count.put(a[i], 1);
            }
            if (count.get(a[i]) > maxFreq)
            {
                maxFreq = count.get(a[i]);
                minlen = i - freqCount.get(a[i]) + 1;
                winindex = freqCount.get(a[i]);
            }
            else if ((count.get(a[i]) == maxFreq) && (i - freqCount.get(a[i]) + 1 < minlen))
            {
                minlen = i - freqCount.get(a[i]) + 1;
                winindex = freqCount.get(a[i]);
            }
        }
        for (int i = winindex; i < winindex + minlen; i++)
            System.out.print(a[i] + " ");
    }
    public static void main (String[] args)
    {
        int arr[] = { 1, 2, 2, 2, 1 };
        int n = arr.length;
        frequentSubArray(arr, n);
    }
}
2 2 2

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ subarray ຂະ ໜາດ ນ້ອຍທີ່ສຸດດ້ວຍອົງປະກອບທີ່ພົບເລື້ອຍທີ່ສຸດ

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ເອກະສານ