ഭൂരിപക്ഷ ഘടകം ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ അത്ലഷിഅന് ബ്ലൂംബർഗ് ഫേസ്ബുക്ക് GoDaddy, ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ വിഭാഗം Snapchat യാഹൂ സെനിഫിറ്റുകൾ
ഭിന്നിപ്പിച്ചു കീഴടക്കുക ഹാഷിംഗ്

പ്രശ്നം പ്രസ്താവന

ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി പൂർണ്ണസംഖ്യകളുടെ. Fl the ഫ്ലോർ ഓപ്പറേറ്ററായ അറേയിൽ ⌊N / 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, ശ്രേണിയിൽ:
    • ഇൻക്രിമെന്റും ആവൃത്തി [i] അല്ലെങ്കിൽ സജ്ജമാക്കുക ആവൃത്തി [i] = 0 അത് ഇതിനകം പട്ടികയിൽ ഇല്ലെങ്കിൽ
    •  If ആവൃത്തി [i] > N / 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

ഭൂരിപക്ഷ ഘടകത്തിന്റെ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) ഭൂരിപക്ഷ ഘടകം കണ്ടെത്തുന്നതിന് ഞങ്ങൾ ഒരു തവണ അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ. N = അറേയുടെ വലുപ്പം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) അറേയിലെ വ്യത്യസ്‌ത ഘടകങ്ങളുടെ പരമാവധി എണ്ണം ഇതായിരിക്കാം: N - ⌊N / 2⌋ ഭൂരിപക്ഷ മൂലകം കുറഞ്ഞത് ഉൾക്കൊള്ളുന്നതിനാൽ N / 2⌋ സൂചികകൾ. അതിനാൽ, സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.

സമീപനം (ബോയർ-മൂർ വോട്ടിംഗ് അൽ‌ഗോരിതം)

ഘടകങ്ങളുടെ ഒരു സ്ട്രീമിൽ ഭൂരിപക്ഷ ഘടകം എങ്ങനെ കണ്ടെത്താമെന്നതിന്റെ മികച്ച ചിത്രീകരണമാണ് ഈ പ്രശ്നം. ഒരു ശ്രേണിയിൽ ⌊N / 2⌋ ൽ കൂടുതൽ സ്ഥലങ്ങൾ ഉൾക്കൊള്ളുന്ന ഘടകം കണ്ടെത്താൻ ബോയർ-മൂർ വോട്ടിംഗ് അൽ‌ഗോരിതം ഉപയോഗിക്കുന്നു. ഈ അൽ‌ഗോരിതം a നിലനിർത്തുന്നു കാൻഡിഡേറ്റ് അതിന്റെ എണ്ണുക ശ്രേണിയിൽ. ഞങ്ങൾ അറേയുടെ ഒരൊറ്റ പാസ് ഉപയോഗിച്ച് പ്രവർത്തിപ്പിക്കുന്നു കാൻഡിഡേറ്റ് = -1 ഒപ്പം എണ്ണുക = 0. അറേയിലെ ഏതെങ്കിലും മൂലകം ആണെങ്കിൽ കാൻഡിഡേറ്റ്, ഞങ്ങൾ വർദ്ധിപ്പിക്കുന്നു എണ്ണം. അല്ലെങ്കിൽ, ഞങ്ങൾ അത് കുറയ്ക്കുന്നു. എണ്ണം പൂജ്യമാകുകയാണെങ്കിൽ, ഞങ്ങൾ അത് മാറ്റുന്നു കാൻഡിഡേറ്റ് അത് സജ്ജമാക്കുക എണ്ണുക 0 ലേക്ക് മടങ്ങുക.

അതിന്റെ പ്രവർത്തനം മനസിലാക്കാൻ, ചുവടെയുള്ള ഉദാഹരണം പിന്തുടരുക:

ഭൂരിപക്ഷ ഘടകം ലീറ്റ്കോഡ് പരിഹാരം

ഈ അൽ‌ഗോരിതം പ്രക്രിയയെ ഒരു തിരഞ്ഞെടുപ്പായി കണക്കാക്കുകയും ആദ്യം ഒരു സ്ഥാനാർത്ഥിയെ തീരുമാനിക്കുകയും ചെയ്യുന്നു. ഏറ്റവും കൂടുതൽ വോട്ട് നേടുന്നയാൾ ഭൂരിപക്ഷ സ്ഥാനാർത്ഥിയാണ്. മുകളിലുള്ള ഉദാഹരണത്തിൽ, ഞങ്ങൾ തുടക്കത്തിൽ ഒരു സ്ഥാനാർത്ഥിയെ 1 ആയി തിരഞ്ഞെടുക്കുന്നു, പക്ഷേ അറേയിലെ സൂചിക 4 ൽ എത്തുമ്പോൾ, ആ എണ്ണം = 0 ഞങ്ങൾ നിരീക്ഷിക്കുന്നു, അതിനർത്ഥം സ്ഥാനാർത്ഥികളല്ലാത്തവരായി ഞങ്ങൾ നിരവധി സ്ഥാനാർത്ഥികളെ കണ്ടിട്ടുണ്ട് എന്നാണ്. അതിനാൽ, ഞങ്ങൾ നിലവിലെ ഘടകത്തെ ഒരു കാൻഡിഡേറ്റായി തിരഞ്ഞെടുത്ത് പ്രക്രിയ തുടരുന്നു. ഞങ്ങൾ ആയതിനാൽ ഗ്യാരണ്ടി അറേയിൽ ഭൂരിപക്ഷ ഘടകം ലഭിക്കാൻ, ഞങ്ങൾക്ക് ശേഷിക്കുന്ന അവസാന സ്ഥാനാർത്ഥി ഭൂരിപക്ഷ ഘടകമായിരിക്കും.

അൽഗോരിതം

  1. രണ്ട് വേരിയബിളുകൾ സമാരംഭിക്കുക: കാൻഡിഡേറ്റ് ഒപ്പം കറ്റലോണിയയിലെ ബന്ധപ്പെട്ട ആവർത്തനങ്ങൾക്കായി കാൻഡിഡേറ്റും അതിന്റെ ആവൃത്തിയും സംഭരിക്കുന്നതിന്
  2. ഇപ്പോൾ, ഓരോ ഘടകത്തിനും i ശ്രേണിയിൽ:
    • If കറ്റലോണിയയിലെ പൂജ്യത്തിന് തുല്യമാണ്:
      • അപ്ഡേറ്റ്: സ്ഥാനാർത്ഥി = 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

ഭൂരിപക്ഷ ഘടകത്തിന്റെ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) ഞങ്ങൾ മുഴുവൻ അറേയും ഒരു തവണ സഞ്ചരിക്കുമ്പോൾ. ഇവിടെ, N = അറേയുടെ വലുപ്പം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) ഞങ്ങൾ സ്ഥിരമായ മെമ്മറി ഇടം ഉപയോഗിക്കുന്നതിനാൽ.