כּולל דופּליקאַט וו לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן facebook גוגל
אַלגערידאַמז מענגע קאָדירונג האַשינג אינטערוויו interviewprep LeetCode LeetCodeSolutions סליידינג ווינדאָו

פּראָבלעם סטאַטעמענט  

אין דעם פּראָבלעם מיר באַקומען אַן מענגע פון ינטאַדזשערז און מיר האָבן צו קאָנטראָלירן אויב עס איז קיין דופּליקאַט עלעמענט וואָס זענען בייַ מינדסטער דיסטאַנסע k איינעם צום צוויטען.
דאס הייסט דער חילוק צווישן די ינדאַסיז פון די צוויי זעלביקער עלעמענטן זאָל זיין ווייניקער ווי גלייַך צו ק.
אָדער,  נומערן [i] == נומס [j] און אַבס (ij) <= ק

בייַשפּיל

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

דערקלערונג:

עלעמענט ביי אינדעקס 0 און 3 איז זעלביקער, און 3 - 0 <= k.

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

צוגאַנג 1 (ברוט פאָרס)  

אויב מיר רעדן וועגן ברוט קראַפט צוגאַנג, מיר קענען פשוט ינסטרומענט דעם פּראָגראַם מיט צוויי לופּס און טשעק פֿאַר יעדער עלעמענט פון דער מענגע צו אַ ווייַטקייט K רעכט פֿון עס צי עס איז קיין עלעמענט פאָרשטעלן אָדער נישט.
אויב קיין עלעמענט איז געפֿונען זעלביקער צו די קראַנט עלעמענט, מיר אומקערן אמת אַנדערש מיר קערן פאַלש.

אַלגאָריטהם

  1. לויפן אַ שלייף פֿאַר יעדער עלעמענט נומערן [i] פון די געגעבן מענגע.
  2. ין דעם שלייף ווידער לויפן אַ פֿאַר שלייף און דורך אַלע די עלעמענטן פֿון j = איך + 1 צו j = i + ק און פאַרגלייַכן זייַן ווערט צו די נומס [איך].
    • If נומערן [j] == נומס [i] דעמאָלט צוריקקומען אמת. ווי מיר האָבן געפֿונען אַן עלעמענט.
  3. לעסאָף ווען קיין דופּליקאַט עלעמענט איז געפֿונען, קערט פאַלש איידער איר פאַרלאָזן די פונקציע.
זע אויך
וואסער לאגלען לעעטקאָדע סאַלושאַן

ימפּלעמענטאַטיאָן פֿאַר כּולל דופּליקאַט וו לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

#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

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר כּולל דופּליקאַט וו לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (n * מין (k, n)): מיר דורכפאָר מינן (k, n) עלעמענטן פֿאַר יעדער עלעמענט פון דער מענגע. דער צייט קאַמפּלעקסיטי וועט זיין אָ (n * מין (k, n)).

ספעיס קאַמפּלעקסיטי 

אָ (1): קעסיידערדיק פּלאַץ.

צוגאַנג 2 (סליידינג פֿענצטער)  

ווי מיר קענען זען מיר גיין מער ווי איין מאָל צו די יסודות פון די מענגע וואָס ינקריסיז די צייט קאַמפּלעקסיטי. מיר זאָל נאָר באַזוכן יעדער עלעמענט איין מאָל צו רעדוצירן די צייט צו O (n).

פֿאַר וואָס מיר קענען טאָן מיר קענען האַלטן אַ סליידינג פֿענצטער פון די פריערדיקע k עלעמענטן ניצן אַ האַש באַשטעטיקט יעדער מאָל ווען מיר באַזוכן קיין עלעמענט פון דער מענגע. דורך דעם, מיר קענען לייכט קאָנטראָלירן פֿון דעם גאַנג פון פריערדיקע ק עלעמענטן אויב עס איז אַן עלעמענט אין דעם גאַנג וואָס איז די זעלבע ווי די קראַנט עלעמענט וואָס מיר באַזוכן. אויב מיר געפֿונען איין אין שטעלן, מיר קומען אמת. אַנדערש מיר וועלן אַרייַן די קראַנט עלעמענט אין דעם גאַנג און אויך באַזייַטיקן די לעצטע באזוכט עלעמענט פֿון דעם גאַנג אַזוי אַז מיר שטענדיק האָבן k פרייַערדיק עלעמענטן אין אונדזער גאַנג.

זע אויך
פּאַסקאַל ס טרייאַנגגאַל וו לעעטקאָדע סאַלושאַן

לאָמיר זען אַ ביישפּיל אין די פיגור אונטן:

כּולל דופּליקאַט וו לעעטקאָדע סאַלושאַןשפּילקע

אַלגאָריטהם

  1. שאַפֿן אַ האַש באַשטעטיקט פֿאַר סטאָרינג k פרייַערדיק עלעמענטן.
  2. דורכפאָר פֿאַר יעדער עלעמענט נומס [i] פון די געגעבן מענגע אין אַ שלייף.
    • קוק אויב האַש שטעלן כּולל נומס [i] אָדער נישט. אויב נומס [i] איז פאָרשטעלן אין דעם סכום (דופּליקאַט עלעמענט איז פאָרשטעלן אין ווייַטקייט ווייניקער ווי גלייַך צו k ), דעמאָלט צוריקקומען אמת. אַנדערש לייגן נומס [i] צו דעם גאַנג.
    • אויב די גרייס פון דעם סכום ווערט גרעסער ווי ק, באַזייַטיקן די לעצטע באזוכט עלעמענט (נומס [ik]) פֿון דעם גאַנג.
  3. לעסאָף ווען קיין דופּליקאַט עלעמענט איז געפֿונען, קערט פאַלש איידער איר פאַרלאָזן די פונקציע.

ימפּלעמענטאַטיאָן פֿאַר כּולל דופּליקאַט וו לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

#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

Java פּראָגראַם

#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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר כּולל דופּליקאַט וו לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (n): ווען מיר באַזוכן יעדער עלעמענט נאָר אַמאָל און אַסומינג אַז אַדינג אַן עלעמענט און רימוווינג אַן עלעמענט נעמט קעסיידערדיק צייט אין האַש שטעלן צייט קאַמפּלעקסיטי רידוסט צו פּונקט O (n).

ספעיס קאַמפּלעקסיטי 

אָ (מין (ק, ן)): מיר סטאָרד ק עלעמענטן ביי מאַקס אין די האַש שטעלן. אויב k> n, בלויז n עלעמענט וועט זיין סטאָרד אין די סכום אין מאַקס.