ਬਹੁਗਿਣਤੀ ਐਲੀਮੈਂਟ II ਲੀਟਕੋਡ ਹੱਲ  


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਡੋਬ ਐਮਾਜ਼ਾਨ ਸੇਬ ਬਲੂਮਬਰਗ ਫੇਸਬੁੱਕ ਗੂਗਲ Microsoft ਦੇ ਜ਼ੈਨੀਫਿਟਸ
ਐਲਗੋਰਿਥਮ ਅਰੇ ਕੋਡਿੰਗ ਇੰਟਰਵਿਊ ਇੰਟਰਵਿ interview ਦੀ ਤਿਆਰੀ ਲੀਟਕੋਡ LeetCodeSolutions

ਇਸ ਸਮੱਸਿਆ ਵਿੱਚ, ਸਾਨੂੰ ਇੱਕ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ ਐਰੇ ਪੂਰਨ ਅੰਕ ਦਾ. ਟੀਚਾ ਉਹਨਾਂ ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਲੱਭਣਾ ਹੈ ਜੋ ਵੱਧ ਤੋਂ ਵੱਧ ਹੁੰਦੇ ਹਨ ⌊N / 3⌋ ਐਰੇ ਦਾ ਸਮਾਂ ਜਿੱਥੇ ਐਰੇ ਦਾ N = ਆਕਾਰ ਅਤੇ ⌊ ⌋ ਫਲੋਰ ਓਪਰੇਟਰ ਹੈ. ਸਾਨੂੰ ਅਜਿਹੇ ਤੱਤਾਂ ਦੀ ਲੜੀ ਵਾਪਸ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਤੱਤਾਂ ਦੀ ਸੀਮਾ: -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 ਲੀਟਕੋਡ ਸਲਿ Sਸ਼ਨ ਦੀ ਸਥਾਪਨਾ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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 ਬਹੁਗਿਣਤੀ ਤੱਤ ਇਸ ਵਾਰ.

ਬਾਇਅਰ-ਮੂਰ ਦੀ ਵੋਟਿੰਗ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਅਸੀਂ ਪਹਿਲਾਂ ਹੀ ਬਹੁਗਿਣਤੀ ਤੱਤ ਦੀ ਸਮੱਸਿਆ ਦਾ ਹੱਲ ਕਰ ਚੁੱਕੇ ਹਾਂ. ਇੱਕ ਬਹੁਗਿਣਤੀ ਤੱਤ ਦੇ ਮਾਮਲੇ ਵਿੱਚ, ਅਸੀਂ ਮੌਜੂਦਾ ਤੱਤ ਉਮੀਦਵਾਰ ਹਨ ਜਾਂ ਨਹੀਂ, ਦੀ ਤੁਲਨਾ ਕਰਕੇ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰ ਸਕਦੇ ਹਾਂ. ਪਰ, ਇਸ ਸਥਿਤੀ ਵਿੱਚ, ਸਾਨੂੰ ਦੋ ਸੰਭਾਵੀ ਬਹੁਗਿਣਤੀ ਤੱਤ ਰੱਖਣ ਅਤੇ ਉਨ੍ਹਾਂ ਦੇ ਕਾtersਂਟਰ ਨੂੰ ਸਮਾਂਤਰ ਅਪਡੇਟ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਸ ਸਹਿਜਤਾ ਦੀ ਸਹਾਇਤਾ ਨਾਲ, ਅਸੀਂ ਆਪਣੀਆਂ ਸ਼ਰਤਾਂ ਨੂੰ ਹੇਠਾਂ ਦਰਸਾ ਸਕਦੇ ਹਾਂ:

  • ਐਰੇ ਵਿੱਚ ਤੱਤ ਦੀ ਸੀਮਾ ਤੋਂ ਬਾਹਰ ਕੋਈ ਵੀ ਬੇਤਰਤੀਬ ਉਮੀਦਵਾਰ ਸੈਟ ਕਰੋ.
  • ਜੇ ਤੱਤ ਕਿਸੇ ਵੀ ਉਮੀਦਵਾਰ ਦੇ ਬਰਾਬਰ ਹੈ, ਤਾਂ ਇਸਦੇ ਕਾ counterਂਟਰ ਨੂੰ ਵਧਾਓ.
  • ਜੇ ਇਕ ਉਮੀਦਵਾਰ ਦਾ ਕਾ counterਂਟਰ ਬਰਾਬਰ ਹੈ ਕਿਸੇ ਵੀ ਬਿੰਦੂ 'ਤੇ, ਅਸੀਂ ਮੌਜੂਦਾ ਤੱਤ ਨੂੰ ਉਮੀਦਵਾਰ ਵਜੋਂ ਤਹਿ ਕਰਦੇ ਹਾਂ if ਇਹ ਮੌਜੂਦਾ ਤੱਤ ਹੋਰ ਉਮੀਦਵਾਰ ਨਹੀਂ ਹੈ.
  • ਅਸੀਂ ਦੋਵੇਂ ਉਮੀਦਵਾਰਾਂ ਦੇ ਕਾ theਂਟਰਾਂ ਨੂੰ ਘਟਾਉਂਦੇ ਹਾਂ ਜੇ ਮੌਜੂਦਾ ਤੱਤ ਕਿਸੇ ਵੀ ਉਮੀਦਵਾਰ ਦੇ ਬਰਾਬਰ ਨਹੀਂ ਹੁੰਦਾ.

ਇਸ ਤਰ੍ਹਾਂ, ਅਸੀਂ ਪਹਿਲੇ ਦੋ ਉਮੀਦਵਾਰਾਂ ਨੂੰ ਪ੍ਰਭਾਵਿਤ ਕੀਤੇ ਬਗੈਰ ਐਰੇ ਵਿਚ ਦੋ ਵੱਖੋ ਵੱਖਰੇ ਉਮੀਦਵਾਰਾਂ ਨੂੰ ਸਮਾਨ ਰੂਪ ਵਿਚ ਬਣਾਈ ਰੱਖਦੇ ਹਾਂ. ਹਾਲਾਂਕਿ, ਇਹ ਸੰਭਵ ਹੈ ਕਿ ਜਿਨ੍ਹਾਂ ਉਮੀਦਵਾਰਾਂ ਦੇ ਨਾਲ ਅਸੀਂ ਅੰਤ ਕਰਦੇ ਹਾਂ ਉਹ ਅਸਲ ਬਹੁਗਿਣਤੀ ਤੱਤ ਨਹੀਂ ਹੁੰਦੇ ({1, 1, 2, 2, 3, 3 one ਇਕ ਅਜਿਹੀ ਉਦਾਹਰਣ ਹੈ). ਇਸ ਲਈ, ਉਮੀਦਵਾਰਾਂ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਗਿਣਨ ਲਈ ਇਕ ਦੂਸਰਾ ਪਾਸ ਚਲਾਉਣਾ ਜ਼ਰੂਰੀ ਹੈ ਜਿਸਦੀ ਸਾਡੇ ਨਾਲ ਅੰਤ ਹੈ. ਇਸਦੇ ਅਧਾਰ ਤੇ, ਅਸੀਂ ਬਹੁਗਿਣਤੀ ਤੱਤਾਂ ਦਾ ਵੈਕਟਰ ਵਾਪਸ ਕਰ ਸਕਦੇ ਹਾਂ.

ਇਹ ਵੀ ਵੇਖੋ
ਬਾਈਨਰੀ ਲੀਟਕੋਡ ਘੋਲ ਸ਼ਾਮਲ ਕਰੋ

ਐਲਗੋਰਿਥਮ

  1. ਸ਼ੁਰੂ ਕਰੋ ਕੈਂਡਨ ਅਤੇ ਕੈਂਡੀ ਦੋ ਉਮੀਦਵਾਰਾਂ ਅਤੇ ਉਨ੍ਹਾਂ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਸੀ ਐਨ ਟੀ ਅਤੇ ਸੀ ਐਨ ਟੀ as .
  2. ਹਰ ਤੱਤ ਲਈ ਐਰੇ ਵਿੱਚ:
    • If ਕੈਂਡਨ == ਆਈ:
      • ਸੀ ਐਨ ਟੀ++
    • ਹੋਰ ਜੇ ਚਾਂਦੀ == i
      • ਸੀ ਐਨ ਟੀ++
    • ਹੋਰ ਜੇ ਸੀ.ਐੱਨਇਕੋ == 0
      • ਨਿਰਧਾਰਤ ਕਰੋ i as ਕੈਂਡਨ: candOne = i
      • ਇਸਦੀ ਗਿਣਤੀ 1 ਦੇ ਤੌਰ ਤੇ ਸੈੱਟ ਕਰੋ: cntOne = 1
    • ਹੋਰ ਜੇ cntTwo == 0
      • candTwo = i
      • cntTwo = 1
    • ਦੋਵਾਂ ਉਮੀਦਵਾਰਾਂ ਦੀ ਗਿਰਾਵਟ:
      • cntOne–
      • cntTw–
  3. ਦੂਜੀ ਪਾਸ ਲਈ ਉਨ੍ਹਾਂ ਦੀ ਗਿਣਤੀ ਜ਼ੀਰੋ ਤੇ ਸੈਟ ਕਰੋ: cntOne = 0 ਅਤੇ cntTwo = 0
  4. ਐਰੇ ਦੇ ਹਰ ਤੱਤ ਲਈ:
    • ਜੇ ਇਹ ਕੈਂਡਨ ਓਨ ਦੇ ਬਰਾਬਰ ਹੈ:
      • cntOne ++
    • ਨਹੀਂ ਤਾਂ ਜੇ ਇਹ ਮੋਮ ਦੋ ਦੇ ਬਰਾਬਰ ਹੈ:
      • cntTwo ++
  5. ਇੱਕ ਸੂਚੀ / ਵੈਕਟਰ ਦੀ ਸ਼ੁਰੂਆਤ ਕਰੋ ਇਸ ਦਾ ਨਤੀਜਾ ਬਹੁਗਿਣਤੀ ਤੱਤ ਸਟੋਰ ਕਰਨ ਲਈ
  6. ਜੇ ਸੀ ਐਨ ਟੀ> ਐਨ / 3
    • ਪੁਸ਼ ਕੈਂਡਨ ਨੂੰ ਇਸ ਦਾ ਨਤੀਜਾ
  7. ਜੇ ਸੀ ਐਨ ਟੀ ਦੋ> ਐਨ / 3
    • ਪੁਸ਼ ਚਾਂਦੀ ਨੂੰ ਇਸ ਦਾ ਨਤੀਜਾ
  8. ਨਤੀਜਾ ਪ੍ਰਿੰਟ ਕਰੋ

ਉਦਾਹਰਣ:

ਬਹੁਗਿਣਤੀ ਐਲੀਮੈਂਟ II ਲੀਟਕੋਡ ਹੱਲਪਿੰਨ

ਬਹੁਮਤ ਐਲੀਮੈਂਟ II ਲੀਟਕੋਡ ਸਲਿ Sਸ਼ਨ ਦੀ ਸਥਾਪਨਾ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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) ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਨਿਰੰਤਰ ਮੈਮੋਰੀ ਸਪੇਸ ਰੱਖਦੇ ਹਾਂ.

1