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


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਸੇਬ Atlassian ਬਲੂਮਬਰਗ ਫੇਸਬੁੱਕ GoDaddy ਗੂਗਲ Microsoft ਦੇ ਓਰੇਕਲ ਭਾਗ Snapchat ਯਾਹੂ ਜ਼ੈਨੀਫਿਟਸ
ਵੰਡੋ ਅਤੇ ਜਿੱਤੋ ਹੈਸ਼ਿੰਗ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਾਨੂੰ ਇੱਕ ਦਿੱਤਾ ਗਿਆ ਹੈ ਐਰੇ ਪੂਰਨ ਅੰਕ ਦਾ. ਸਾਨੂੰ ਪੂਰਨ ਅੰਕ ਵਾਪਸ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਜੋ ਐਰੇ ਵਿੱਚ ⌊N / 2⌋ ਵਾਰ ਤੋਂ ਵੱਧ ਸਮੇਂ ਤੇ ਹੁੰਦੀ ਹੈ ਜਿੱਥੇ floor the ਫਲੋਰ ਸੰਚਾਲਕ ਹੁੰਦਾ ਹੈ. ਇਸ ਤੱਤ ਨੂੰ ਬਹੁਗਿਣਤੀ ਤੱਤ ਕਿਹਾ ਜਾਂਦਾ ਹੈ. ਨੋਟ ਕਰੋ ਕਿ ਇਨਪੁਟ ਐਰੇ ਵਿੱਚ ਹਮੇਸ਼ਾਂ ਇੱਕ ਬਹੁਮਤ ਤੱਤ ਹੁੰਦਾ ਹੈ.

ਉਦਾਹਰਨ

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, ਐਰੇ ਵਿਚ:
    • ਵਾਧਾ ਬਾਰੰਬਾਰਤਾ [i] ਜਾਂ ਸੈੱਟ ਕਰੋ ਬਾਰੰਬਾਰਤਾ [i] = 0 ਜੇ ਇਹ ਪਹਿਲਾਂ ਹੀ ਟੇਬਲ ਵਿਚ ਨਹੀਂ ਹੈ
    •  If ਬਾਰੰਬਾਰਤਾ [i] > ਐਨ / 2:
      • ਵਾਪਸੀ i
  3. ਵਾਪਸੀ -1 (ਸੰਕਲਨ ਅਸ਼ੁੱਧੀ ਤੋਂ ਬਚਣ ਲਈ)
  4. ਨਤੀਜਾ ਪ੍ਰਿੰਟ ਕਰੋ

ਬਹੁਗਿਣਤੀ ਐਲੀਮੈਂਟ ਲੀਟਕੋਡ ਹੱਲ ਦੀ ਸਥਾਪਨਾ

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

#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;
}

ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ

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 / 2⌋ ਕਿਉਂਕਿ ਬਹੁਗਿਣਤੀ ਤੱਤ ਘੱਟੋ ਘੱਟ ਕਾਬਜ਼ ਹੈ ⌊N / 2⌋ ਸੂਚਕਾਂਕ. ਇਸ ਲਈ, ਸਪੇਸ ਦੀ ਗੁੰਝਲਤਾ ਰੇਖਿਕ ਹੈ.

ਪਹੁੰਚ (ਬੁਅਰ-ਮੂਰ ਵੋਟਿੰਗ ਐਲਗੋਰਿਦਮ)

ਇਹ ਸਮੱਸਿਆ ਇਕ ਵਧੀਆ ਉਦਾਹਰਣ ਹੈ ਕਿ ਅਸੀਂ ਤੱਤ ਦੀ ਧਾਰਾ ਵਿਚ ਬਹੁਮਤ ਤੱਤ ਕਿਵੇਂ ਪਾ ਸਕਦੇ ਹਾਂ. ਬਾਇਅਰ-ਮੂਰ ਵੋਟਿੰਗ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਇਕ ਤੱਤ ਨੂੰ ਲੱਭਣ ਲਈ ਕੀਤੀ ਜਾਂਦੀ ਹੈ ਜੋ ਇਕ ਤਰਤੀਬ ਵਿਚ ⌊N / 2⌋ ਤੋਂ ਵੱਧ ਸਥਾਨਾਂ 'ਤੇ ਕਬਜ਼ਾ ਕਰਦਾ ਹੈ. ਇਹ ਐਲਗੋਰਿਦਮ ਨੂੰ ਕਾਇਮ ਰੱਖਦਾ ਹੈ a ਦੇ ਉਮੀਦਵਾਰ ਅਤੇ ਇਸ ਦੇ ਦੀ ਗਿਣਤੀ ਐਰੇ ਵਿੱਚ. ਅਸੀਂ ਇਸ ਨਾਲ ਐਰੇ ਦਾ ਇਕੋ ਪਾਸ ਚਲਾਉਂਦੇ ਹਾਂ ਦੇ ਉਮੀਦਵਾਰ = -1 ਅਤੇ ਦੀ ਗਿਣਤੀ = 0. ਜੇ ਐਰੇ ਵਿਚ ਕੋਈ ਤੱਤ ਹੈ ਦੇ ਉਮੀਦਵਾਰ, ਸਾਨੂੰ ਵਾਧਾ ਗਿਣਤੀ. ਨਹੀਂ ਤਾਂ, ਅਸੀਂ ਇਸ ਨੂੰ ਘਟਾਉਂਦੇ ਹਾਂ. ਜੇ ਗਿਣਤੀ ਜ਼ੀਰੋ ਹੋ ਜਾਂਦੀ ਹੈ, ਅਸੀਂ ਬਦਲੋ ਦੇ ਉਮੀਦਵਾਰ ਅਤੇ ਇਸ ਨੂੰ ਸੈੱਟ ਕਰੋ ਦੀ ਗਿਣਤੀ ਵਾਪਸ 0 ਤੇ.

ਇਸਦੇ ਕੰਮਕਾਜ ਨੂੰ ਸਮਝਣ ਲਈ, ਹੇਠਾਂ ਦਿੱਤੀ ਉਦਾਹਰਣ ਦੀ ਪਾਲਣਾ ਕਰੋ:

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

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

ਐਲਗੋਰਿਥਮ

  1. ਦੋ ਪਰਿਵਰਤਨ ਅਰੰਭ ਕਰੋ: ਦੇ ਉਮੀਦਵਾਰ ਅਤੇ cnt ਉਮੀਦਵਾਰ ਅਤੇ ਇਸਦੀ ਬਾਰੰਬਾਰਤਾ ਲਈ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ
  2. ਹੁਣ, ਹਰ ਤੱਤ ਲਈ i ਐਰੇ ਵਿੱਚ:
    • If cnt ਜ਼ੀਰੋ ਦੇ ਬਰਾਬਰ ਹੈ:
      • ਅਪਡੇਟ ਕਰੋ: ਉਮੀਦਵਾਰ = i
    • If i ਬਰਾਬਰ ਹੈ ਦੇ ਉਮੀਦਵਾਰ:
      • ਵਾਧਾ cnt: ਸੀ ਐਨ ਟੀ ++
    • ਹੋਰ:
      • ਕਮੀ cnt: ਸੀ ਐਨ ਟੀ
  3. ਵਾਪਸੀ ਦੇ ਉਮੀਦਵਾਰ
  4. ਨਤੀਜਾ ਪ੍ਰਿੰਟ ਕਰੋ

ਬਹੁਗਿਣਤੀ ਐਲੀਮੈਂਟ ਲੀਟਕੋਡ ਹੱਲ ਦੀ ਸਥਾਪਨਾ

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

#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;
}

ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ

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 ਐਰੇ ਦਾ ਆਕਾਰ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1) ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਨਿਰੰਤਰ ਮੈਮੋਰੀ ਸਪੇਸ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ.