ಬಹುಪಾಲು ಎಲಿಮೆಂಟ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


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

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಸರಣಿ ಪೂರ್ಣಾಂಕಗಳ. ಹೆಚ್ಚು ಸಂಭವಿಸುವ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಗುರಿಯಾಗಿದೆ ⌊N / 3⌋ ರಚನೆಯ ಸಮಯ N = ರಚನೆಯ ಗಾತ್ರ ಮತ್ತು ⌊ the ನೆಲದ ಆಪರೇಟರ್. ಅಂತಹ ಅಂಶಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನಾವು ಹಿಂತಿರುಗಿಸಬೇಕಾಗಿದೆ.

ಅಂಶಗಳ ಶ್ರೇಣಿ: -10 ^ 9 ಗೆ 10 ^ 9

ಉದಾಹರಣೆ

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

ವಿವರಣೆ⌊N / 3⌋ = ⌊5 / 3⌋ = 1. ಈಗ, 2 ಮತ್ತು 3 ಪೂರ್ಣಾಂಕಗಳು 2 ಕ್ಕೆ ಸಮನಾದ ಆವರ್ತನಗಳನ್ನು ಹೊಂದಿವೆ, ಅದು ಹೆಚ್ಚಾಗಿದೆ 1. ಆದ್ದರಿಂದ, ನಾವು ಅವುಗಳನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ.

Array = {1 , 2 , 3 , 4}
No majority elements

ವಿವರಣೆ: ಈ ಸಂದರ್ಭದಲ್ಲಿ ಆವರ್ತನ 1 ಕ್ಕಿಂತ ಹೆಚ್ಚಿರುವ ಯಾವುದೇ ಅಂಶವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಲಿಲ್ಲ. ಆದ್ದರಿಂದ, ನಾವು “ಬಹುಸಂಖ್ಯಾತ ಅಂಶಗಳಿಲ್ಲ” ಎಂದು ಮುದ್ರಿಸುತ್ತೇವೆ.

ಅಪ್ರೋಚ್ (ಆವರ್ತನಗಳನ್ನು ಸಂಗ್ರಹಿಸುವುದು)

ಶೀರ್ಷಿಕೆಯು ಸೂಚಿಸುವಂತೆ, ನಾವು ಹ್ಯಾಶ್ ಟೇಬಲ್ ಬಳಸಿ ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶದ ಆವರ್ತನವನ್ನು ಸಂಗ್ರಹಿಸಬಹುದು ಮತ್ತು ನಂತರ ಆವರ್ತನಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಅಂಶಗಳನ್ನು ಪರಿಶೀಲಿಸಬಹುದು ⌊N / 3⌋. ಈ ರೀತಿಯಾಗಿ, ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುವ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ನಾವು ಕಾಣಬಹುದು.

ಕ್ರಮಾವಳಿ

  1. ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ-ಆವರ್ತನ ರಚನೆಯಲ್ಲಿನ ಅಂಶಗಳ ಆವರ್ತನಗಳನ್ನು ಮತ್ತು ಪಟ್ಟಿ / ವೆಕ್ಟರ್ ಅನ್ನು ಸಂಗ್ರಹಿಸಲು ಫಲಿತಾಂಶ ಬಹುಪಾಲು ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು
  2. ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಶ್ರೇಣಿಯಲ್ಲಿ:
    • ಅದರ ಆವರ್ತನವನ್ನು ಹೆಚ್ಚಿಸಿ: ಆವರ್ತನ [i] ++ (ಅಥವಾ ಈಗಾಗಲೇ ಇಲ್ಲದಿದ್ದರೆ 1 ಎಂದು ಹೊಂದಿಸಿ)
  3. ಪ್ರತಿಯೊಬ್ಬರಿಗೂ ಪ್ರಮುಖ ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ನಲ್ಲಿ:
    1. If ಆವರ್ತನ [ಕೀ] > ಎನ್ / 3
      1. ಇದನ್ನು ಸೇರಿಸಿ ಫಲಿತಾಂಶ
  4. ಪಟ್ಟಿಯನ್ನು ಹಿಂತಿರುಗಿ ಫಲಿತಾಂಶ

ಮೆಜಾರಿಟಿ ಎಲಿಮೆಂಟ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಅನುಷ್ಠಾನ

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

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

vector<int> majorityElement(vector<int>& a)
{
    int N = a.size();
    vector <int> result;
    unordered_map <int , int> frequency;
    for(int &x : a)
        frequency[x]++;
    for(auto &x : frequency)
        if(x.second > N / 3)
            result.emplace_back(x.first);
    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

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

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashMap <Integer , Integer> frequency = new HashMap <>();

        for(int i = 0 ; i < a.length ; i++)
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);

        for(Map.Entry i : frequency.entrySet())
        {
            Integer value = (int)i.getValue() , key = (int)i.getKey();
            if((int)value > ((a.length) / 3))
                result.add(key);
        }
        return result;
    }
}
2 3

ಮೆಜಾರಿಟಿ ಎಲಿಮೆಂಟ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್) ಆವರ್ತನಗಳನ್ನು ನವೀಕರಿಸಲು ನಾವು ಒಮ್ಮೆ ಇಡೀ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ. N = ರಚನೆಯ ಗಾತ್ರ.

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

ಒ (ಎನ್) ಆವರ್ತನಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಹ್ಯಾಶ್ ಟೇಬಲ್ ಬಳಸುತ್ತಿದ್ದಂತೆ.

ಅನುಸಂಧಾನ (ಬೋಯರ್-ಮೂರ್ ಮತದಾನ ಅಲ್ಗಾರಿದಮ್)

ಇಲ್ಲಿ ಗಮನಿಸಬೇಕಾದ ಮೊದಲ ವಿಷಯವೆಂದರೆ, ಆವರ್ತನಕ್ಕಿಂತ ಹೆಚ್ಚಿನ 2 ಅಂಶಗಳು ಇರಬಹುದು ರಚನೆಯಲ್ಲಿ ⌊N / 3⌋. ಆದ್ದರಿಂದ, ಈ ಸಮಸ್ಯೆ ಒಂದೇ ಆಗುತ್ತದೆ ಬಹುಮತದ ಅಂಶ ಸಮಸ್ಯೆ 2 ಈ ಸಮಯದಲ್ಲಿ ಬಹುಪಾಲು ಅಂಶಗಳು.

ಬೋಯರ್-ಮೂರ್ ಅವರ ಮತದಾನ ಅಲ್ಗಾರಿದಮ್ ಬಳಸಿ ನಾವು ಈಗಾಗಲೇ ಮೆಜಾರಿಟಿ ಎಲಿಮೆಂಟ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಿದ್ದೇವೆ. ಒಂದೇ ಬಹುಮತದ ಅಂಶದ ಸಂದರ್ಭದಲ್ಲಿ, ಪ್ರಸ್ತುತ ಅಂಶವು ಅಭ್ಯರ್ಥಿಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಹೋಲಿಸುವ ಮೂಲಕ ನಾವು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಬಹುದು. ಆದರೆ, ಈ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಎರಡು ಸಂಭಾವ್ಯ ಬಹುಮತದ ಅಂಶಗಳನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳಬೇಕು ಮತ್ತು ಅವುಗಳ ಕೌಂಟರ್‌ಗಳನ್ನು ಸಮಾನಾಂತರವಾಗಿ ನವೀಕರಿಸಬೇಕು. ಈ ಅಂತಃಪ್ರಜ್ಞೆಯ ಸಹಾಯದಿಂದ, ನಾವು ನಮ್ಮ ಪರಿಸ್ಥಿತಿಗಳನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಹೊಂದಿಸಬಹುದು:

  • ಯಾವುದೇ ಎರಡು ಯಾದೃಚ್ om ಿಕ ಅಭ್ಯರ್ಥಿಗಳನ್ನು ರಚನೆಯ ಅಂಶಗಳ ವ್ಯಾಪ್ತಿಯಿಂದ ಹೊರಗೆ ಹೊಂದಿಸಿ.
  • ಅಂಶವು ಎರಡೂ ಅಭ್ಯರ್ಥಿಗಳಿಗೆ ಸಮನಾಗಿದ್ದರೆ, ಅದರ ಕೌಂಟರ್ ಅನ್ನು ಹೆಚ್ಚಿಸಿ.
  • ಒಬ್ಬ ಅಭ್ಯರ್ಥಿಯ ಕೌಂಟರ್ ಸಮಾನವಾಗಿದ್ದರೆ 0 ಯಾವುದೇ ಸಮಯದಲ್ಲಿ, ನಾವು ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಅಭ್ಯರ್ಥಿಯಾಗಿ ಹೊಂದಿಸುತ್ತೇವೆ if ಈ ಪ್ರಸ್ತುತ ಅಂಶವು ಇತರ ಅಭ್ಯರ್ಥಿಯಲ್ಲ.
  • ಪ್ರಸ್ತುತ ಅಂಶವು ಎರಡೂ ಅಭ್ಯರ್ಥಿಗಳಿಗೆ ಸಮನಾಗಿರದಿದ್ದರೆ ನಾವು ಎರಡೂ ಅಭ್ಯರ್ಥಿಗಳ ಕೌಂಟರ್‌ಗಳನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತೇವೆ.

ಈ ರೀತಿಯಾಗಿ, ಮೊದಲ ಅಭ್ಯರ್ಥಿಯು ಇನ್ನೊಬ್ಬರ ಮೇಲೆ ಪರಿಣಾಮ ಬೀರದಂತೆ ನಾವು ಎರಡು ವಿಭಿನ್ನ ಅಭ್ಯರ್ಥಿಗಳನ್ನು ರಚನೆಯಲ್ಲಿ ಸಮಾನಾಂತರವಾಗಿ ನಿರ್ವಹಿಸುವುದನ್ನು ಮುಂದುವರಿಸುತ್ತೇವೆ. ಆದಾಗ್ಯೂ, ನಾವು ಕೊನೆಗೊಳ್ಳುವ ಅಭ್ಯರ್ಥಿಗಳು ನಿಜವಾದ ಬಹುಮತದ ಅಂಶಗಳಲ್ಲ ({1, 1, 2, 2, 3, 3 such ಅಂತಹ ಒಂದು ಉದಾಹರಣೆಯಾಗಿದೆ). ಆದ್ದರಿಂದ, ನಾವು ಕೊನೆಗೊಳ್ಳುವ ಅಭ್ಯರ್ಥಿಗಳ ಆವರ್ತನಗಳನ್ನು ಎಣಿಸಲು ಎರಡನೇ ಪಾಸ್ ಅನ್ನು ಚಲಾಯಿಸುವುದು ಅವಶ್ಯಕ. ಇದರ ಆಧಾರದ ಮೇಲೆ, ನಾವು ಬಹುಪಾಲು ಅಂಶಗಳ ವೆಕ್ಟರ್ ಅನ್ನು ಹಿಂತಿರುಗಿಸಬಹುದು.

ಕ್ರಮಾವಳಿ

  1. ಪ್ರಾರಂಭಿಸಿ ಕ್ಯಾಂಡನ್ ಒನ್ ಮತ್ತು ಕ್ಯಾಂಡ್ಟ್ವೋ ಇಬ್ಬರು ಅಭ್ಯರ್ಥಿಗಳು ಮತ್ತು ಅವರ ಆವರ್ತನಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು cntOne ಮತ್ತು cntTwo as 0.
  2. ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಶ್ರೇಣಿಯಲ್ಲಿ:
    • If candOne == i:
      • cntOne++
    • ಇಲ್ಲದಿದ್ದಲ್ಲಿ ಕ್ಯಾಂಡ್ ಟೂ == i
      • cntTwo++
    • ಇಲ್ಲದಿದ್ದರೆ ಸಿಎನ್tOne == 0
      • ನಿಗದಿಪಡಿಸಿ i as ಕ್ಯಾಂಡನ್ ಒನ್: candOne = i
      • ಅದರ ಸಂಖ್ಯೆಯನ್ನು 1 ಎಂದು ಹೊಂದಿಸಿ: cntOne = 1
    • ಇಲ್ಲದಿದ್ದಲ್ಲಿ cntTwo == 0
      • candTwo = i
      • cntTwo = 1
    • ಎರಡೂ ಅಭ್ಯರ್ಥಿಗಳ ಇಳಿಕೆ ಎಣಿಕೆಗಳು:
      • cntOne–
      • cntTwo–
  3. ಎರಡನೇ ಪಾಸ್‌ಗಾಗಿ ಅವರ ಎಣಿಕೆಗಳನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಿ: cntOne = 0 ಮತ್ತು cntTwo = 0
  4. ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ:
    • ಅದು ಕ್ಯಾಂಡೊನ್‌ಗೆ ಸಮನಾಗಿದ್ದರೆ:
      • cntOne ++
    • ಅದು ಕ್ಯಾಂಡ್‌ಟೂಗೆ ಸಮನಾಗಿದ್ದರೆ:
      • cntTwo ++
  5. ಪಟ್ಟಿ / ವೆಕ್ಟರ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ ಫಲಿತಾಂಶ ಬಹುಪಾಲು ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು
  6. CntOne> N / 3 ಆಗಿದ್ದರೆ
    • ಪುಶ್ ಕ್ಯಾಂಡನ್ ಒನ್ ಗೆ ಫಲಿತಾಂಶ
  7. CntTwo> N / 3 ಆಗಿದ್ದರೆ
    • ಪುಶ್ ಕ್ಯಾಂಡ್ ಟೂ ಗೆ ಫಲಿತಾಂಶ
  8. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ವಿವರಣೆ:

ಬಹುಪಾಲು ಎಲಿಮೆಂಟ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಮೆಜಾರಿಟಿ ಎಲಿಮೆಂಟ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಅನುಷ್ಠಾನ

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

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

vector <int> majorityElement(vector <int> &a)
{
    vector <int> result;
    int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
    for(int &i : a)
    {
        if(candOne == i)
            cntOne++;
        else if(candTwo == i)
            cntTwo++;
        else if(cntOne == 0)
        {
            candOne = i;
            cntOne++;
        }
        else if(cntTwo == 0)
        {
            candTwo = i;
            cntTwo++;
        }
        else
        {
            cntOne--;
            cntTwo--;
        }
    }

    cntOne = 0;
    cntTwo = 0;
    for(int &i : a)
    {
        if(i == candOne)
            cntOne++;
        if(i == candTwo)
            cntTwo++;
    }

    if(cntOne > ((int)a.size()) / 3)
        result.push_back(candOne);
    if(cntTwo > ((int)a.size()) / 3)
        result.push_back(candTwo);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

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

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList<>();

        int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
        for(int i : a)
        {
            if(candOne == i)
                cntOne++;
            else if(candTwo == i)
                cntTwo++;
            else if(cntOne == 0)
            {
                candOne = i;
                cntOne++;
            }
            else if(cntTwo == 0)
            {
                candTwo = i;
                cntTwo++;
            }
            else
            {
                cntOne--;
                cntTwo--;
            }
        }

        cntOne = 0;
        cntTwo = 0;
        for(int i : a)
        {
            if(i == candOne)
                cntOne++;
            if(i == candTwo)
                cntTwo++;
        }

        if(cntOne > (a.length) / 3)
            result.add(candOne);
        if(cntTwo > (a.length) / 3)
            result.add(candTwo);

        return result;
    }
}
3 2

ಮೆಜಾರಿಟಿ ಎಲಿಮೆಂಟ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್) ಇನ್ಪುಟ್ ಅನ್ನು ಲೆಕ್ಕಿಸದೆ ನಾವು ರಚನೆಯ ಎರಡು ಪಾಸ್ಗಳನ್ನು ಚಲಾಯಿಸುತ್ತೇವೆ. N = ರಚನೆಯ ಗಾತ್ರ.

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

ಒ (1) ನಾವು ಸ್ಥಿರ ಮೆಮೊರಿ ಸ್ಥಳದಂತೆ.