ಕೊಟ್ಟಿರುವ ರಚನೆಯು ಪರಸ್ಪರ ದೂರದಲ್ಲಿರುವ ಕೆ ದೂರದಲ್ಲಿ ನಕಲಿ ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಅವಲಾರಾ ಸಿಟಾಡೆಲ್ ಫ್ರೀಚಾರ್ಜ್ ಹ್ಯಾಕರ್ರ್ಯಾಂಕ್ Snapchat ಸ್ನ್ಯಾಪ್ಡಿಯಲ್
ಅರೇ ಹ್ಯಾಶ್

"ಕೊಟ್ಟಿರುವ ರಚನೆಯು ಪರಸ್ಪರ ದೂರದಲ್ಲಿರುವ ಕೆ ಅಂತರದಲ್ಲಿ ನಕಲಿ ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ" ಎಂಬ ಸಮಸ್ಯೆಯು ಕೆ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಕೊಟ್ಟಿರುವ ಕ್ರಮವಿಲ್ಲದ ಶ್ರೇಣಿಯಲ್ಲಿನ ನಕಲುಗಳಿಗಾಗಿ ನಾವು ಪರಿಶೀಲಿಸಬೇಕಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಇಲ್ಲಿ k ಯ ಮೌಲ್ಯವು ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಗಿಂತ ಚಿಕ್ಕದಾಗಿದೆ.

ಕೊಟ್ಟಿರುವ ರಚನೆಯು ಪರಸ್ಪರ ದೂರದಲ್ಲಿರುವ ಕೆ ದೂರದಲ್ಲಿ ನಕಲಿ ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ

ಉದಾಹರಣೆಗಳು

K = 3   arr[] = {1, 2, 3, 4, 5, 2, 1}
False
K = 2   arr[] = {3, 4, 3, 1, 1, 2, 6}
True

ವಿವರಣೆ

ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ನಮಗೆ ಎರಡು ವಿಧಾನಗಳಿವೆ. ಎರಡು ಲೂಪ್‌ಗಳನ್ನು ಚಲಾಯಿಸುವುದು ಸರಳವಾದದ್ದು, ಇದರಲ್ಲಿ ಮೊದಲ ಲೂಪ್ ಪ್ರತಿ ಅಂಶವನ್ನು ಎರಡನೇ ಲೂಪ್ 'ಇನ್ನರ್ ಲೂಪ್'ಗೆ ಆರಂಭಿಕ ಅಂಶವಾಗಿ ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಅದರ ನಂತರ, ಎರಡನೇ ಲೂಪ್ ಆರಂಭಿಕ ಅಂಶವನ್ನು 'ಕೆ' ವ್ಯಾಪ್ತಿಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಅಂಶಗಳೊಂದಿಗೆ ಹೋಲಿಸುತ್ತದೆ. ಆದರೆ ಈ ಪರಿಹಾರವು ಪರಿಣಾಮಕಾರಿಯಾಗಿಲ್ಲ ಅದು O (k * n) ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ.

ಆದರೆ ನಮ್ಮಲ್ಲಿ ಮತ್ತೊಂದು ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿ ವಿಧಾನವಿದೆ, ಅದು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತದೆ ಓ (ಎನ್) ಸಮಯದ ಸಂಕೀರ್ಣತೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಹ್ಯಾಶಿಂಗ್. ಹ್ಯಾಶಿಂಗ್ ವಿಧಾನದಲ್ಲಿ, ನಾವು ರಚನೆಯ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಅದರಲ್ಲಿ ಅಂಶವಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅಂಶವು ಅಲ್ಲಿದ್ದರೆ ನಾವು 'ನಿಜ' ಎಂದು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ. ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಅದನ್ನು ಹ್ಯಾಶ್‌ಗೆ ಸೇರಿಸುತ್ತೇವೆ ಮತ್ತು 'ನಾನು' 'ಕೆ' ಗಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ ಅಥವಾ ಸಮನಾಗಿದ್ದರೆ ಹ್ಯಾಶ್‌ನಿಂದ ಆರ್ [ಐಕ್] ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕುತ್ತೇವೆ.

ಕೊಟ್ಟಿರುವ ರಚನೆಯು ಪರಸ್ಪರ ದೂರದಲ್ಲಿರುವ ಕೆ ದೂರದಲ್ಲಿ ನಕಲಿ ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವ ಅಲ್ಗಾರಿದಮ್

  1. ಮೊದಲು, ಖಾಲಿ ರಚಿಸಿ ಹ್ಯಾಶ್ ಸೆಟ್ ಇದರಲ್ಲಿ ನಾವು ರಚನೆಯ ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.
  2. ರಚನೆಯ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಎಡದಿಂದ ಬಲಕ್ಕೆ ಹಾದುಹೋಗಿರಿ.
  3. ಅಂಶವು ಹ್ಯಾಶ್‌ನಲ್ಲಿದೆ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಪರಿಶೀಲಿಸಿ.
    • ಅದು ಅಲ್ಲಿದ್ದರೆ “ನಿಜ” ಎಂದು ಹಿಂತಿರುಗಿ.
    • ಇಲ್ಲದಿದ್ದರೆ ಆ ಅಂಶವನ್ನು ಹ್ಯಾಶ್‌ಗೆ ಸೇರಿಸಿ.
  4. ಅದರ ನಂತರ 'ನಾನು' ದೊಡ್ಡದಾಗಿದ್ದರೆ ಅಥವಾ 'ಕೆ' ಗೆ ಸಮನಾಗಿದ್ದರೆ ಹ್ಯಾಶ್‌ನಿಂದ ಆರ್ [ಐಕ್] ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕಿ.

 

ನಮ್ಮಲ್ಲಿ 'ಆರ್ []' ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಹೊಂದಿದೆ ಮತ್ತು ಅದರಲ್ಲಿ ಒಂದು ಕೆ ಮೌಲ್ಯವಿದೆ, ಅದು ಯಾವುದಾದರೂ ಇದ್ದರೆ ನಾವು ನಕಲುಗಳನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾದ ಶ್ರೇಣಿಯಾಗಿದೆ, ಆದ್ದರಿಂದ ಅದರಲ್ಲಿರುವ ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಹ್ಯಾಶ್ ಸೆಟ್ ಅನ್ನು ಬಳಸುತ್ತೇವೆ ಮೊದಲು ನಾವು ಅಂಶಗಳನ್ನು ಸೇರಿಸುತ್ತೇವೆ ಅಂಶವು ಈಗಾಗಲೇ ಹ್ಯಾಶ್ ಸೆಟ್ನಲ್ಲಿದ್ದರೆ ನಮ್ಮ ಹ್ಯಾಶ್‌ನಲ್ಲಿನ ರಚನೆಯು ಒಂದೊಂದಾಗಿ ಹೊಂದಿಸಲ್ಪಡುತ್ತದೆ, ಅದು ನಿಜಕ್ಕೆ ಮರಳುತ್ತದೆ ಮತ್ತು ಲೂಪ್ ಅನ್ನು ಮುರಿಯುತ್ತದೆ, ಇಲ್ಲದಿದ್ದರೆ ಅದು ನಿರಂತರವಾಗಿ ಸೆಟ್ನಲ್ಲಿರುವ ಅಂಶಗಳನ್ನು ಸೇರಿಸುತ್ತದೆ ಮತ್ತು ಸೆಟ್‌ನಿಂದ ಆರ್ [ಐಕ್] ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ.

ಕೋಡ್

ಕೊಟ್ಟಿರುವ ರಚನೆಯು ಪರಸ್ಪರ ದೂರದಲ್ಲಿರುವ ಕೆ ದೂರದಲ್ಲಿ ನಕಲಿ ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಸಿ ++ ಕೋಡ್

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

bool Check_Duplicates(int a[], int n, int k)
{

    unordered_set<int> D_set;

    for (int i = 0; i < n; i++)
    {
        if (D_set.find(a[i]) != D_set.end())
            return true;

        D_set.insert(a[i]);
        if (i >= k)
            D_set.erase(a[i-k]);
    }
    return false;
}

int main ()
{
    int a[] = {1, 2, 3, 4, 1};
    int k = 5;
    cout << ((Check_Duplicates(a, 5, k)) ? "Yes" : "No");
}
Yes

ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯು ಪರಸ್ಪರ ದೂರದಲ್ಲಿರುವ ಕೆ ದೂರದಲ್ಲಿ ನಕಲಿ ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಜಾವಾ ಕೋಡ್

import java.util.*;
class D_Class
{
    static boolean Check_Duplicates(int a[], int k)
    {

        HashSet<Integer> D_set = new HashSet<>();

        for (int i=0; i<a.length; i++)
        {
            if (D_set.contains(a[i]))
                return true;

            D_set.add(a[i]);
            if (i >= k)
                D_set.remove(a[i-k]);
        }
        return false;
    }

    public static void main (String[] args)
    {
        int a[] = {1, 2, 3, 4, 1};
        int k = 5;

        if (Check_Duplicates(a, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

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

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

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

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

ಸರಿ) ಅಲ್ಲಿ “ಕೆ” ವಿಂಡೋದಲ್ಲಿ ನೋಡಬೇಕಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆ.