ત્રીજી મહત્તમ સંખ્યા લિટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન ફેસબુક Google
અરે

શીર્ષક કહે છે તેમ, આપેલમાં ત્રીજું મહત્તમ પૂર્ણાંક શોધવાનું લક્ષ્ય છે એરે પૂર્ણાંકોની. નોંધો કે આપણે આ શોધવાની જરૂર છે અલગ એરેમાં ત્રીજો મહત્તમ પૂર્ણાંક. જ્યારે મહત્તમ પૂર્ણાંકો એરેમાં મહત્તમ પૂર્ણાંક ન હોય ત્યારે અમે એરેમાં પાછા ફરો.

ઉદાહરણ

Array = {1 , 3 , 2 , -2 , -4 , -9}
1

સમજૂતી

પ્રથમ મહત્તમ 3, બીજી મહત્તમ 2 અને ત્રીજી મહત્તમ 1 છે. તેથી, આપણે 1 છાપીશું.

Array = {1 , 1 , 3}
3

સમજૂતી

પ્રથમ મહત્તમ 3 છે, બીજી મહત્તમ 1 છે, પરંતુ ત્યાં છે નં ત્રીજી મહત્તમ કારણ કે આપણે બંને 1 ને અહીં બીજા મહત્તમ માને છે.

અભિગમ (સortર્ટિંગ)

આપણે આખા એરેને સ sortર્ટ કરી શકીએ છીએ ત્રીજી અલગ પૂર્ણાંક તેનાથી શરૂ થાય છે પાછા. નોંધ લો કે આપણે એરે [N - 3] ને પાછા આપી શકતા નથી કારણ કે એરેમાં ડુપ્લિકેટ પ્રવેશો હોઈ શકે છે. જો અમને ન મળે 3 એરેમાં સ્પષ્ટ પૂર્ણાંકો, અમે તેનો છેલ્લો તત્વ પરત કરીએ છીએ કારણ કે તે મહત્તમ તત્વ છે. સારી સમજ માટે આપેલ અલ્ગોરિધમનો અનુસરો.

ત્રીજી મહત્તમ સંખ્યા લિટકોડ સોલ્યુશન

અલ્ગોરિધમ

  1. ફંકશન બનાવો થર્ડમેક્સ () જરૂરી પૂર્ણાંક પરત આપવો
  2. થર્ડમેક્સ () આપેલ એરેમાં ત્રીજો અલગ મહત્તમ પૂર્ણાંકો આપે છે. a
  3. એરે સortર્ટ કરો
  4. ચલ શરૂ કરો, આઈડીએક્સ એરેના છેલ્લા ઇન્ડેક્સને સંગ્રહિત કરવા અને ડિફેક્ટકાઉન્ટ પાછળ થી અલગ તત્વો ગણવા માટે
  5. જ્યારે idx> = 0:
    • વધારો ડિફેક્ટકાઉન્ટ
    • પ્રારંભ કરો સૂચકનું પુનરાવર્તન કરવું જે એક સમાન મૂલ્ય ધરાવતું સૂચક છે.
    • જ્યારે તત્વો પહેલાં આઈડીએક્સ [idx] ની સમાન કિંમત છે અને i> = 0:
      • ઘટાડો i
    • If i == -1, તેનો અર્થ એ કે અમે આખા એરેને વટાવી દીધા છે
      • એરે [n - 1], મહત્તમ તત્વ પરત કરો કારણ કે એરેમાં 3 ત્રણ અલગ તત્વો પણ નહોતા
    • સોંપો આઈડીએક્સ = આઇ મહત્તમ પૂર્ણાંકોના આગલા સેટ પર જવા માટે
    • If ડિફેક્ટકાઉન્ટ 2 ની બરાબર છે,
      • તેનો અર્થ એ કે આપણે વર્તમાન તત્વ કરતા 2 મોટા તત્વો તપાસ્યા છે (a [idx])
      • વર્તમાન તત્વ પાછો, એક [આઇડીએક્સ]
  6.  ફંક્શન સિન્ટેક્સ ખાતર, વળતર -1.
  7. પરિણામ છાપો

ત્રીજી મહત્તમ સંખ્યા લિટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

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

int thirdMax(vector <int> &a)
{
    int n = a.size();
    sort(a.begin() , a.end());

    int idx = n - 1 , i , distinctCount = 0;

    while(idx >= 0)
    {
        distinctCount++;
        i = idx - 1;
        //to check all the values with same value as a[idx]
        while(i >= 0 && a[i] == a[idx])
            i--;

        //no third distinct element
        if(i == -1)
            return a[n - 1];
        idx = i;

        //found 2 bigger elements before?
        if(distinctCount == 2)
            return a[idx];
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

જાવા પ્રોગ્રામ

import java.util.Arrays;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        int n = a.length;
        Arrays.sort(a);

        int idx = n - 1 , i , distinctCount = 0;

        while(idx >= 0)
        {
            distinctCount++;
            i = idx - 1;
            //to check all the values with same value as a[idx]
            while(i >= 0 && a[i] == a[idx])
                i--;

            //no third distinct element
            if(i == -1)
                return a[n - 1];
            idx = i;

            //found 2 bigger elements before?
            if(distinctCount == 2)
                return a[idx];
        }
        return -1;
    }
}
1

ત્રીજા મહત્તમ સંખ્યા લિટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

O (NlogN), N = એરેનું કદ, જેમ કે આપણે આખા એરેને સ sortર્ટ કરીએ છીએ.

જગ્યાની જટિલતા

ઓ (1) આપણે ફક્ત સતત મેમરી જગ્યા વાપરીએ છીએ.

અભિગમ (શ્રેષ્ઠ)

અહીં શ્રેષ્ઠ અભિગમ ફક્ત ત્રણ મૂલ્યો જાળવવાનો છે જે એરેમાં પ્રથમ, બીજા અને ત્રીજા મહત્તમ પૂર્ણાંકો સંગ્રહિત કરશે. જો કે, કેટલાક આધાર કિસ્સાઓ છે જેમ કે આપણે હંમેશાં અલગ અલગ તત્વોને મહત્તમ તરીકે ધ્યાનમાં લેવું જોઈએ. આ હેતુ માટે, સમૂહ નો ઉપયોગ કરી શકાય છે જેથી આપણે હંમેશાં ડુપ્લિકેટ તત્વોથી છૂટકારો મેળવી શકીએ. આપણે એરે દ્વારા પુનરાવર્તિત થઈ શકીએ છીએ અને તેનું કદ જાળવી શકીએ છીએ સમૂહ દરેક પુનરાવર્તન પછી 3 કોઈ પણ નિવેશ પછી તેમાં 3 થી વધુ તત્વો હોય તો, અમે તેમાંથી ઓછામાં ઓછું તત્વ પ popપ આઉટ કરીએ છીએ જેથી તે ત્રણ શામેલ હોય અલગ અલગ અંતે તત્વો. જો અંતમાં તેનું કદ 3 કરતા ઓછું હોય, તો અમે તેનું મહત્તમ મૂલ્ય પાછું આપીશું.

અલ્ગોરિધમ

  1. ફરીથી આપણે એ જ ફંકશન વાપરીએ છીએ થર્ડમેક્સ () અમારી સમસ્યા હલ કરવા માટે
  2. મહત્તમ પૂર્ણાંકો સંગ્રહવા માટે એક સેટ પ્રારંભ કરો.
  3. બધા માટે તત્વ એરેમાં:
    • તેને સેટમાં ઉમેરો
    • જો સમૂહનું કદ 3 કરતા વધારે છે
      • સેટમાં ઓછામાં ઓછું તત્વ ભૂંસી નાંખો / દૂર કરો
  4. જો સમૂહનું કદ 3 ની બરાબર છે
    • તેમાંથી ઓછામાં ઓછું તત્વ પરત કરો
  5. બીજું
    • તેમાં મહત્તમ તત્વ પરત કરો
  6. પરિણામ છાપો

ત્રીજી મહત્તમ સંખ્યા લિટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

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

int thirdMax(vector <int> &a)
{
    set <int> maxElements;
    for(int &element : a)
    {
        maxElements.insert(element);
        if(maxElements.size() > 3)
            maxElements.erase(*maxElements.begin());
    }
    if(maxElements.size() == 3)
        return *maxElements.begin();

    return *prev(maxElements.end());
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

જાવા પ્રોગ્રામ

import java.util.*;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        Set <Integer> maxElements = new HashSet <>();
        for(int element : a)
        {
            maxElements.add(element);
            if(maxElements.size() > 3)
                maxElements.remove(Collections.min(maxElements));
        }

        if(maxElements.size() == 3)
            return Collections.min(maxElements);
        return Collections.max(maxElements);
    }
}
1

ત્રીજા મહત્તમ સંખ્યા લિટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) આપણે એક પાસમાં એરે દ્વારા ફરીએ છીએ. સેટમાં તત્વોને કાtionી નાખવા અને દાખલ કરવામાં સતત સમય લે છે, કારણ કે આપણે દરેક પુનરાવૃત્તિ પછી તેમાં વધુમાં વધુ 3 તત્વો જાળવીએ છીએ. અહીં, N એરેનું = કદ.

જગ્યાની જટિલતા

ઓ (1) આપણે ફક્ત સતત મેમરી જગ્યા વાપરીએ છીએ.