מערהייט עלעמענט לעעטקאָדע סאַלושאַן  


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

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

מיר זענען געגעבן אַן מענגע פון ינטאַדזשערז. מיר דאַרפֿן צו צוריקקומען די גאַנץ נומער וואָס אַקערז מער ווי ⌊ ן / 2⌋ צייט אין די מענגע ווו ⌊ ⌋ איז די שטאָק אָפּעראַטאָר. דער עלעמענט איז גערופן די מערהייט עלעמענט. באַמערקונג אַז די אַרייַנשרייַב מענגע שטענדיק כּולל אַ מערהייט עלעמענט.

בייַשפּיל

Array = {1 , 3 , 3 , 3}
3

עקסאַפּלאַנאַטיאָן: ⌊N / 2⌋ = 4/2 = 2. און די ינטאַדזשער '3' אַקערז 3 מאָל אין די מענגע.

Array = {1 , 1 , 2}
1

דערקלערונג: ⌊N / 2⌋ = ⌊3 / 2⌋ = 1. און '1' אַקערז 2 מאָל אין די מענגע.

צוגאַנג (האַשטאַבלע)  

מיר קענען קראָם די אָפטקייַט פון יעדער עלעמענט אין די האַש טיש. עס איז גרינג צו קאָנטראָלירן אַ גאַנץ נומער פון אָפטקייַט> ⌊N / 2⌋.

אַלגאָריטהם

  1. יניטיאַליזירן אַ האַש טיש צו קראָם די אָפטקייַט פון ינטאַדזשערז אין די מענגע: אָפטקייַט
  2. פֿאַר יעדער עלעמענט, i, אין די מענגע:
    • Increment אָפטקייַט [i] אָדער שטעלן אָפטקייַט [איך] = 0 אויב עס איז נישט אין די טיש שוין
    •  If אָפטקייַט [i] > N / 2:
      • צוריקקומען איך
  3. ווייַזן -1 (צו ויסמיידן קאָמפּילאַטיאָן טעות)
  4. דרוק דעם רעזולטאַט

ימפּלאַמענטיישאַן פון די Majority Element Leetcode סאַלושאַן

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

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

int majorityElement(vector <int> &a)
{
    int majorityCount = ((int) a.size()) / 2;
    unordered_map <int , int> frequency;
    for(int &i : a)
    {
        if(++frequency[i] > majorityCount)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

Java פּראָגראַם

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        HashMap <Integer , Integer> frequency = new HashMap<>();
        for(int i = 0 ; i < a.length ; i++)
        {
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);
            if(frequency.get(a[i]) > a.length / 2)
                return a[i];
        }
        return -1;
    }
}
2

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

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

אָ (N) ווען מיר דורכפאָר די מענגע אַמאָל צו געפֿינען די מערהייט עלעמענט. N = גרייס פון דעם מענגע.

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

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

אָ (N) ווי די מאַקסימום נומער פון בוילעט עלעמענטן אין די מענגע קענען זיין: N - ⌊N / 2⌋ ווי די מערהייט עלעמענט אַקיאַפּייז לפּחות ⌊ ן / 2 ינדיסעס. דעריבער, די פּלאַץ קאַמפּלעקסיטי איז לינעאַר.

צוגאַנג (שטימען אַלגערידאַם פון בויער-מאָר 

דער פּראָבלעם איז אַ פייַן יללוסטראַטיאָן פון ווי מיר קענען געפֿינען אַ מערהייט עלעמענט אין אַ טייַך פון עלעמענטן. די בויער-מאָר אָפּשטימונג אַלגערידאַם איז געניצט צו געפֿינען דעם עלעמענט וואָס אַקיאַפּייז מער ווי ⌊ ן / 2 ⌋ ערטער אין אַ סיקוואַנס. דעם אַלגערידאַם מיינטיינז אַ קאַנדידאַט און זייַן ציילן אין די מענגע. מיר פירן אַ איין פאָרן פון די מענגע מיט קאַנדידאַט = -1 און ציילן = 0. אויב קיין עלעמענט אין די מענגע איז די קאַנדידאַט, מיר ינקראַמאַנט ציילן. אַנדערש מיר דיקריסט עס. אויב דער ציילן ווערט נול, מיר טוישן די קאַנדידאַט און שטעלן זייַן ציילן צוריק צו 0.

נאָכפאָלגן די אונטן ביישפּיל צו פֿאַרשטיין די פאַנגקשאַנז:

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

דער אַלגערידאַם באַטראַכטן דעם פּראָצעס ווי אַ וואַלן און ערשטער דיסיידז אַ קאַנדידאַט. דער וואס באקומט די מערסטע שטימען איז דער מערהייט קאנדידאט. אין דעם אויבן ביישפּיל, מיר קלייַבן אַ קאַנדידאַט אין ערשטן 1, אָבער ווען מיר דערגרייכן אינדעקס 4 אין די מענגע, מיר באמערקן אַז ציילן = 0, וואָס מיטל אַז מיר האָבן געזען ווי פילע קאַנדאַדייץ ווי ניט-קאַנדאַדייץ. אַזוי, מיר קלייַבן די קראַנט עלעמענט ווי אַ קאַנדידאַט און פאָרזעצן דעם פּראָצעס. זינט מיר זענען געראַנטיד צו האָבן אַ מערהייט עלעמענט אין די מענגע, די לעצטע קאַנדידאַט וואָס מיר האָבן לינקס איז די מערהייט עלעמענט.

אַלגאָריטהם

  1. ערשט צוויי וועריאַבאַלז: קאַנדידאַט און קנט צו קראָם די קאַנדידאַט און זיין אָפטקייַט פֿאַר ריספּעקטיוו יטעריישאַנז
  2. איצט, פֿאַר יעדער עלעמענט i אין די מענגע:
    • If קנט איז גלייך צו נול:
      • דערהייַנטיקן: קאַנדידאַט = איך
    • If i איז גלייך צו קאַנדידאַט:
      • ינקראַמאַנט קנט: cnt ++
    • אלזא:
      • דעקרעד קנט: קונץ -
  3. צוריקקומען קאַנדידאַט
  4. דרוק דעם רעזולטאַט
זע אויך
געפֿינען די סומע פון ​​ניט-ריפּיטינג עלעמענטן (בוילעט) עלעמענטן אין אַ מענגע

ימפּלאַמענטיישאַן פון די Majority Element Leetcode סאַלושאַן

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

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

int majorityElement(vector <int> &a)
{
    int candidate = -1 , cnt = 0;
    for(int &i : a)
    {
        if(cnt == 0)
            candidate = i;
        cnt += (candidate == i) ? 1 : -1;
    }
    return candidate;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

Java פּראָגראַם

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        int candidate = -1 , cnt = 0;
        for(int i = 0 ; i < a.length ; i++)
        {
            if(cnt == 0)
                candidate = a[i];
            cnt += (candidate == a[i]) ? 1 : -1;
        }
        return candidate;
    }
}
2

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

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

אָ (N) ווען מיר דורכפאָר די גאנצע מענגע אַמאָל. דאָ, N = גרייס פון דעם מענגע.

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

אָ (1) ווי מיר נוצן קעסיידערדיק זיקאָרן פּלאַץ.