ನಕಲಿ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಒಳಗೊಂಡಿದೆ


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

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಸರಣಿ ಪೂರ್ಣಾಂಕಗಳ ಮತ್ತು ಕನಿಷ್ಠ ದೂರದಲ್ಲಿರುವ ಯಾವುದೇ ನಕಲಿ ಅಂಶವಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬೇಕು k ಪರಸ್ಪರ.
ಅಂದರೆ ಆ ಎರಡು ಒಂದೇ ಅಂಶದ ಸೂಚ್ಯಂಕಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸವು k ಗೆ ಸಮನಾಗಿರಬೇಕು.
ಅಥವಾ,  ಸಂಖ್ಯೆಗಳು [i] == ಸಂಖ್ಯೆಗಳು [ಜೆ] ಮತ್ತು abs (ij) <= k

ಉದಾಹರಣೆ

nums = [1,2,3,1], k = 3
true

ವಿವರಣೆ:

ಸೂಚ್ಯಂಕ 0 ಮತ್ತು 3 ರಲ್ಲಿನ ಅಂಶವು ಒಂದೇ ಆಗಿರುತ್ತದೆ ಮತ್ತು 3 - 0 <= k.

nums = [1,2,3,1,2,3], k = 2
false

ಅಪ್ರೋಚ್ 1 (ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ)

ನಾವು ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ ವಿಧಾನದ ಬಗ್ಗೆ ಮಾತನಾಡಿದರೆ, ನಾವು ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಎರಡು ಕುಣಿಕೆಗಳನ್ನು ಬಳಸಿ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು ಮತ್ತು ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಯಾವುದಾದರೂ ಅಂಶವಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಕೆ ನಿಂದ ದೂರಕ್ಕೆ ಪರಿಶೀಲಿಸಬಹುದು.
ಯಾವುದೇ ಅಂಶವು ಪ್ರಸ್ತುತ ಅಂಶಕ್ಕೆ ಸಮನಾಗಿ ಕಂಡುಬಂದರೆ ನಾವು ನಿಜವಾಗುತ್ತೇವೆ ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ.

ಕ್ರಮಾವಳಿ

  1. ಪ್ರತಿ ಅಂಶಕ್ಕೂ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ ಸಂಖ್ಯೆಗಳು [i] ಕೊಟ್ಟಿರುವ ರಚನೆಯ.
  2. ಈ ಲೂಪ್ ಒಳಗೆ ಮತ್ತೆ ಲೂಪ್‌ಗಾಗಿ ಒಂದು ರನ್ ಮಾಡಿ ಮತ್ತು ಎಲ್ಲ ಅಂಶಗಳನ್ನು ಹಾದುಹೋಗುತ್ತದೆ j = i + 1 ಗೆ j = i + k ಮತ್ತು ಅದರ ಮೌಲ್ಯವನ್ನು ಹೋಲಿಕೆ ಮಾಡಿ ಸಂಖ್ಯೆಗಳು [i].
    • If ಸಂಖ್ಯೆಗಳು [j] == ಸಂಖ್ಯೆಗಳು [i] ನಂತರ ನಿಜಕ್ಕೆ ಹಿಂತಿರುಗಿ. ನಾವು ಒಂದು ಅಂಶವನ್ನು ಕಂಡುಕೊಂಡಂತೆ.
  3. ಅಂತಿಮವಾಗಿ ಯಾವುದೇ ನಕಲಿ ಅಂಶ ಕಂಡುಬಂದಿಲ್ಲವಾದರೆ ಕಾರ್ಯದಿಂದ ನಿರ್ಗಮಿಸುವ ಮೊದಲು ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿ.

ನಕಲು II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಒಳಗೊಂಡಿರುವ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    for(int i=0;i<nums.size();i++)
        for(int j=i+1;j<nums.size() && j<=i+k;j++)
        {
            if(nums[j]==nums[i])
                return true;
        }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

class Rextester{
    
    public static boolean containsNearbyDuplicate(int[] nums, int k) 
    {
        for(int i=0;i<nums.length;i++)
            for(int j=i+1;j<nums.length && j<=i+k;j++)
            {
                if(nums[j]==nums[i])
                    return true;
            }

        return false;

    }
    
    public static void main(String args[])
    {
       	int[] nums={1,2,3,1};
        int k=3;
        System.out.println(containsNearbyDuplicate(nums,k) );
    }
}
true

ನಕಲಿ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಒಳಗೊಂಡಿರುವ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್ * ನಿಮಿಷ (ಕೆ, ಎನ್)): ನಾವು ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ನಿಮಿಷ (ಕೆ, ಎನ್) ಅಂಶಗಳನ್ನು ಹಾದುಹೋಗುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O (n * min (k, n) ಆಗಿರುತ್ತದೆ.

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

ಒ (1): ಸ್ಥಿರ ಸ್ಥಳ.

ಅಪ್ರೋಚ್ 2 (ಸ್ಲೈಡಿಂಗ್ ವಿಂಡೋ)

ನಾವು ನೋಡುವಂತೆ ನಾವು ರಚನೆಯ ಅಂಶಗಳಿಗೆ ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಬಾರಿ ಹೋಗುತ್ತಿದ್ದೇವೆ ಅದು ಅದರ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ. O (n) ಗೆ ಸಮಯವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ನಾವು ಪ್ರತಿ ಅಂಶಕ್ಕೆ ಒಮ್ಮೆ ಮಾತ್ರ ಭೇಟಿ ನೀಡಬೇಕು.

ಅದಕ್ಕಾಗಿ ನಾವು ಏನು ಮಾಡಬಹುದೆಂದರೆ ನಾವು ಹಿಂದಿನ ಸ್ಲೈಡಿಂಗ್ ವಿಂಡೋವನ್ನು ಇರಿಸಿಕೊಳ್ಳಬಹುದು k ಹ್ಯಾಶ್ ಬಳಸುವ ಅಂಶಗಳು ಪ್ರತಿ ಬಾರಿಯೂ ನಾವು ರಚನೆಯ ಯಾವುದೇ ಅಂಶಕ್ಕೆ ಭೇಟಿ ನೀಡುತ್ತೇವೆ. ಇದನ್ನು ಮಾಡುವುದರ ಮೂಲಕ ನಾವು ಹಿಂದಿನ ಕೆ ಅಂಶಗಳ ಗುಂಪಿನಿಂದ ಸುಲಭವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದು, ಅದು ನಾವು ಭೇಟಿ ನೀಡುತ್ತಿರುವ ಪ್ರಸ್ತುತ ಅಂಶದಂತೆಯೇ ಒಂದು ಅಂಶವಿದೆ. ನಾವು ಸೆಟ್ನಲ್ಲಿ ಒಂದನ್ನು ಕಂಡುಕೊಂಡರೆ, ಆ ಕ್ಷಣದಲ್ಲಿ ನಾವು ನಿಜವಾಗುತ್ತೇವೆ. ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಸೆಟ್ನಲ್ಲಿ ಸೇರಿಸುತ್ತೇವೆ ಮತ್ತು ಕೊನೆಯದಾಗಿ ಭೇಟಿ ನೀಡಿದ ಅಂಶವನ್ನು ಸೆಟ್ನಿಂದ ತೆಗೆದುಹಾಕುತ್ತೇವೆ ಇದರಿಂದ ನಾವು ಯಾವಾಗಲೂ ಹೊಂದಿರುತ್ತೇವೆ k ನಮ್ಮ ಸೆಟ್ನಲ್ಲಿ ಹಿಂದಿನ ಅಂಶಗಳು.

ಕೆಳಗಿನ ಚಿತ್ರದಲ್ಲಿ ಉದಾಹರಣೆಯನ್ನು ನೋಡೋಣ:

ನಕಲಿ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಒಳಗೊಂಡಿದೆ

ಕ್ರಮಾವಳಿ

  1. ಒಂದು ರಚಿಸಿ ಹ್ಯಾಶ್ ಸೆಟ್ ಸಂಗ್ರಹಿಸಲು k ಹಿಂದಿನ ಅಂಶಗಳು.
  2. ಕೊಟ್ಟಿರುವ ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶ ಸಂಖ್ಯೆಗಳಿಗೆ [i] ಲೂಪ್‌ನಲ್ಲಿ ಸಂಚರಿಸಿ.
    • ಹ್ಯಾಶ್ ಸೆಟ್ ಈಗಾಗಲೇ ಸಂಖ್ಯೆಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ [i] ಅಥವಾ ಇಲ್ಲ. ಸಂಖ್ಯೆಯಲ್ಲಿ [i] ಇದ್ದರೆ (ಅಂದರೆ ನಕಲಿ ಅಂಶವು ಸಮಾನಕ್ಕಿಂತ ಕಡಿಮೆ ಅಂತರದಲ್ಲಿರುತ್ತದೆ k ), ನಂತರ ನಿಜಕ್ಕೆ ಹಿಂತಿರುಗಿ. ಇಲ್ಲದಿದ್ದರೆ ಸೆಟ್ಗೆ ಸಂಖ್ಯೆಗಳನ್ನು ಸೇರಿಸಿ [i].
    • ಸೆಟ್ನ ಗಾತ್ರವು k ಗಿಂತ ಹೆಚ್ಚಾಗಿದ್ದರೆ, ಕೊನೆಯದಾಗಿ ಭೇಟಿ ನೀಡಿದ ಅಂಶವನ್ನು (ಸಂಖ್ಯೆಗಳು [ik]) ಸೆಟ್ನಿಂದ ತೆಗೆದುಹಾಕಿ.
  3. ಅಂತಿಮವಾಗಿ ಯಾವುದೇ ನಕಲಿ ಅಂಶ ಕಂಡುಬಂದಿಲ್ಲವಾದರೆ ಕಾರ್ಯದಿಂದ ನಿರ್ಗಮಿಸುವ ಮೊದಲು ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿ.

ನಕಲು II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಒಳಗೊಂಡಿರುವ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

ನಕಲಿ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಒಳಗೊಂಡಿರುವ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್): ನಾವು ಪ್ರತಿ ಅಂಶವನ್ನು ಒಮ್ಮೆ ಮಾತ್ರ ಭೇಟಿ ಮಾಡಿದಾಗ ಮತ್ತು ಒಂದು ಅಂಶವನ್ನು ಸೇರಿಸುವುದು ಮತ್ತು ಒಂದು ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕುವುದು ಹ್ಯಾಶ್ ಸೆಟ್ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಕೇವಲ O (n) ಗೆ ಇಳಿಸುವುದರಲ್ಲಿ ಸ್ಥಿರ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎಂದು uming ಹಿಸುತ್ತೇವೆ.

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

ಒ (ನಿಮಿಷ (ಕೆ, ಎನ್)): ನಾವು ಹ್ಯಾಶ್ ಸೆಟ್ನಲ್ಲಿ ಕೆ ಅಂಶಗಳನ್ನು ಗರಿಷ್ಠವಾಗಿ ಸಂಗ್ರಹಿಸುತ್ತಿದ್ದೇವೆ. K> n ಆಗಿದ್ದರೆ ಗರಿಷ್ಠವಾಗಿ n ಅಂಶವನ್ನು ಮಾತ್ರ ಸೆಟ್ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ.