ಕೆಗಿಂತ ಹೆಚ್ಚು ವಿಶಿಷ್ಟ ಅಂಶಗಳನ್ನು ಹೊಂದಿರದ ಉದ್ದದ ಸಬ್‌ರೇ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಸಿಟಾಡೆಲ್ ದೆಹಲಿ ಫೇಸ್ಬುಕ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಸ್ಯಾಮ್ಸಂಗ್ ಯಾಂಡೆಕ್ಸ್
ಅರೇ ಹ್ಯಾಶ್ ಸ್ಲೈಡಿಂಗ್ ವಿಂಡೋ

"ಕೆಗಿಂತ ಹೆಚ್ಚಿನ ಅಂಶಗಳನ್ನು ಹೊಂದಿರದ ಉದ್ದದ ಸಬ್‌ರೇ" ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ಒಂದು ಇದೆ ಎಂದು ಭಾವಿಸುತ್ತದೆ ಸರಣಿ of ಪೂರ್ಣಾಂಕಗಳು, ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಕೆ ವಿಭಿನ್ನ ಅಂಶಗಳಿಗಿಂತ ಹೆಚ್ಚಿಲ್ಲದ ಉದ್ದದ ಉಪ-ಶ್ರೇಣಿಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ.

ಉದಾಹರಣೆಕೆಗಿಂತ ಹೆಚ್ಚು ವಿಶಿಷ್ಟ ಅಂಶಗಳನ್ನು ಹೊಂದಿರದ ಉದ್ದದ ಸಬ್‌ರೇ

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

ವಿವರಣೆ

ಕೆ ವಿಭಿನ್ನ ಅಂಶಗಳೊಂದಿಗೆ ಉದ್ದವಾದ ಉಪ-ರಚನೆ (2, 1, 2, 0)

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

ವಿವರಣೆ

ಕೆ ವಿಭಿನ್ನ ಅಂಶಗಳೊಂದಿಗೆ ಅತಿ ಉದ್ದದ ಉಪ-ರಚನೆ (3, 4)

ಕ್ರಮಾವಳಿ

  1. ಪ್ರತಿ ಅಂಶದ ಸಂಖ್ಯೆಯನ್ನು ಹೆಚ್ಚಿಸಿ ಮತ್ತು ಇರಿಸಿ
  2. 0 ರಿಂದ ಪ್ರಾರಂಭಿಸಿ ಅದು k ಗಿಂತ ದೊಡ್ಡದಾಗುವವರೆಗೆ ವಿಭಿನ್ನ ಅಂಶಗಳ ಎಣಿಕೆಯನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ.
  3. ಎಣಿಕೆ k ಗಿಂತ ಹೆಚ್ಚಾಗಿದ್ದರೆ, ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಪ್ರಾರಂಭಿಸಿ (ಪ್ರಾರಂಭದ ಹಂತ).
  4. ನಾವು ಮತ್ತೆ ಪಡೆಯುವವರೆಗೆ ಎಣಿಕೆಯನ್ನು ತೆಗೆದುಹಾಕಿ. ಕೆ ವಿಭಿನ್ನ ಅಂಶಗಳು ಉಪ-ರಚನೆಯ ಪ್ರಾರಂಭದ ಹಂತವನ್ನು ಸಹ ಹೆಚ್ಚಿಸುತ್ತವೆ.
  5. ಉದ್ದದ ಉಪ-ರಚನೆಯ ಉದ್ದವನ್ನು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ರಚನೆಯ ಅಂಶ ಸೂಚ್ಯಂಕದ ಪ್ರಕಾರ ಅಂತ್ಯವನ್ನು ನವೀಕರಿಸಿ.
  6. ಎಂಡ್-ಪಾಯಿಂಟ್‌ಗೆ ಪ್ರಾರಂಭವಾಗುವ ಅರೇ ಫಾರ್ಮ್ ಅನ್ನು ಮುದ್ರಿಸಿ.

ವಿವರಣೆ

ನಾವು ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಿದ್ದೇವೆ, ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಅತಿ ಉದ್ದದ ಉಪ-ಶ್ರೇಣಿಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಕೇಳಿದ್ದೇವೆ, ಅದು ಕೆ ವಿಭಿನ್ನ ಅಂಶಗಳಿಗಿಂತ ಹೆಚ್ಚಿಲ್ಲ. ನಾವು ಇದೇ ರೀತಿಯ ವಿಧಾನವನ್ನು ಬಳಸಲಿದ್ದೇವೆ ಹ್ಯಾಶಿಂಗ್. ನಾವು ಪ್ರತಿ ಅಂಶದ ಸಂಖ್ಯೆಯನ್ನು ಹೆಚ್ಚಿಸುತ್ತಲೇ ಇರಬೇಕು, ಆದರೂ ನಾವು ಅತಿ ಉದ್ದದ ಉಪ-ಶ್ರೇಣಿಯನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ. ಆದ್ದರಿಂದ ನಾವು ಉಪ-ರಚನೆಯ ಪ್ರಾರಂಭದ ಹಂತದಲ್ಲಿ ಮತ್ತು ಉಪ-ರಚನೆಯ ಕೊನೆಯ ಹಂತದಲ್ಲಿ ಕಣ್ಣಿಡಬೇಕು. ಆದ್ದರಿಂದ, ನಾವು ಆ ಉಪ-ಶ್ರೇಣಿಯನ್ನು ಪ್ರಾರಂಭದಿಂದ ಕೊನೆಯವರೆಗೆ k ಗಿಂತ ಹೆಚ್ಚು ಭಿನ್ನವಾಗಿ ಮುದ್ರಿಸುವುದಿಲ್ಲ.

ನಾವು ಆ ವಸ್ತುಗಳ ಎಣಿಕೆಯನ್ನು ಸಹ ಕಾಪಾಡಿಕೊಳ್ಳಬೇಕು ಅದು ಯಾವುದೇ ಸಂಖ್ಯೆ k ಗಿಂತ ಹೆಚ್ಚಿರಬಾರದು ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ನಾವು ಒಂದು ಉದಾಹರಣೆಯನ್ನು ತೆಗೆದುಕೊಳ್ಳೋಣ:

ಅರ್ [] = {4, 3, 5, 2, 1, 2, 0, 4, 5}, ಕೆ = 3

ನಾವು ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಆರಿಸುತ್ತೇವೆ ಮತ್ತು ರಚನೆಯ ಅಂಶದ ಎಣಿಕೆಯನ್ನು ಹೆಚ್ಚಿಸುತ್ತೇವೆ ಮತ್ತು ಪ್ರತಿ ಬಾರಿ ಅದರ ಸಂಭವವು ಮೊದಲ ಬಾರಿಗೆ ಆಗಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಿದಾಗ, ನಾವು ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯನ್ನು ಹೆಚ್ಚಿಸುತ್ತೇವೆ, ನಾವು ಅದನ್ನು k ನೊಂದಿಗೆ ಹೋಲಿಸಲಿದ್ದೇವೆ, ನಾವು ಹಾಗೆ ಮಾಡುವುದಿಲ್ಲ ಅದು k ಗಿಂತ ದೊಡ್ಡದಾಗುವವರೆಗೆ ಏನು. ಒಮ್ಮೆ ಅದು k ಗಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ, ನಾವು 0 ರಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಅಂಶದ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತೇವೆ ಮತ್ತು ಮೌಲ್ಯವನ್ನು ಹೆಚ್ಚಿಸುತ್ತೇವೆ ಇದರಿಂದ ಮುಂದಿನ ಬಾರಿ ಮುಂದಿನ ಅಂಶದ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡಬಹುದು. ನಾವು ಎಡದ ಮೌಲ್ಯವನ್ನು ಹೆಚ್ಚಿಸಬೇಕು, ನಾವು ಮತ್ತೆ ಕೆ ವಿಭಿನ್ನ ಅಂಶಗಳನ್ನು ಕಂಡುಕೊಳ್ಳುವವರೆಗೂ ಅದು ಉಪ-ರಚನೆಯ ಪ್ರಾರಂಭದ ಹಂತವಾಗಿರುತ್ತದೆ.

ನಾವು ಒಂದು ಶ್ರೇಣಿಯಿಂದ 4, 3 ಮತ್ತು 5 ಅನ್ನು ಪರಿಗಣಿಸಿದರೆ ನಮ್ಮಲ್ಲಿ i = 2, ಕರ್ರ್ = 3 ಇದೆ, ನಾವು ಮುಂದಿನ ಅಂಶಕ್ಕೆ ಹೋದರೆ ನಾವು ಕರ್ರ್ ಅನ್ನು 4 ಎಂದು ಪಡೆಯುತ್ತೇವೆ ಮತ್ತು ನಾವು 2 ಅನ್ನು ಉಪ-ರಚನೆಯ ಪ್ರಾರಂಭದ ಹಂತವಾಗಿ ಪಡೆಯುತ್ತೇವೆ ಮತ್ತು ನಾವು ಇರಿಸಿಕೊಳ್ಳಬೇಕು 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

ಕೆಗಿಂತ ಹೆಚ್ಚಿನ ಅಂಶಗಳನ್ನು ಹೊಂದಿರದ ಉದ್ದದ ಸಬ್‌ರೇ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಬಳಸುವುದರಿಂದ ಒ (1) ಸಮಯದಲ್ಲಿ ಸೇರಿಸಲು, ಅಳಿಸಲು ಮತ್ತು ಹುಡುಕಲು ಅನುಮತಿಸುತ್ತದೆ. ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಬೇಕಾಗಬಹುದು. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆಯೂ ರೇಖೀಯವಾಗಿರುತ್ತದೆ.