Kth નો પુનરાવર્તિત અક્ષર  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન બ્લૂમબર્ગ ફેસબુક ગોલ્ડમૅન સૅશ Google માઈક્રોસોફ્ટ ઓરેકલ ઝિલો
હેશ હેશિંગ હેશમેપ શબ્દમાળા

સમસ્યા નિવેદન  

“Kth નોન-રિપીટીંગ કેરેક્ટર” માં આપણે એ શબ્દમાળા “ઓ”. Kth નોન-રિપીટીંગ_ચરેક્ટર શોધવા માટે એક પ્રોગ્રામ લખો. જો ત્યાં કે કેરેક્ટર કરતા ઓછા છે જે શબ્દમાળામાં પુનરાવર્તિત નથી, તો પછી “-1” છાપો.

ઇનપુટ ફોર્મેટ  

પ્રથમ અને ફક્ત એક જ લીટી જેમાં શબ્દમાળા "ઓ" શામેલ છે.

આઉટપુટ ફોર્મેટ  

A_character ધરાવતી પ્રથમ અને ફક્ત એક જ લાઇન કે જે kth નોન-રિપીટીંગ_ચરેક્ટરનું પ્રતિનિધિત્વ કરે છે. જો ત્યાં કે કેરેક્ટર કરતા ઓછા છે જે શબ્દમાળામાં પુનરાવર્તિત નથી, તો પછી “-1” છાપો.

ઉદાહરણ  

tutorialcup
3
i

સમજૂતી: અહીં ફ્રીક [ટી] 2 છે, ફ્રીક [યુ] 2 છે, અને બાકીના અન્ય ચારમાં ફ્રીક 1 છે. તેથી Kth નોન-રિપીટિંગ_ચરેક્ટર છે "અથવા".

અલ્ગોરિધમ  

1. એરેમાં અક્ષરોની ગણતરી સંગ્રહવા માટે કાઉન્ટ એરે બનાવો.

2. પુનરાવર્તિત અક્ષરોની અનુક્રમણિકા સંગ્રહવા માટે અનુક્રમણિકા એરે બનાવો.

3. જો કોઈ અક્ષર 'x' પુનરાવર્તન કરે છે અથવા ઇન્ડેક્સ એરેમાં શબ્દમાળા સ્ટોર n માં હાજર નથી.

4. ઝીરો અને ઈન્ડેક્સ એરે સાથે એન સાથે ગણતરી એરે પ્રારંભ કરો. (n એ શબ્દમાળાની લંબાઈ છે)

5. ઇનપુટ શબ્દમાળા x = str [i] ને પસાર કરો

6. વૃદ્ધિ ગણતરી [x]

7. જો ગણતરી [x] = 1, તો પછી અનુક્રમણિકામાં x ની અનુક્રમણિકા સ્ટોર કરો [x]. અનુક્રમણિકા [x] = i

8. જો ગણતરી [x] = 2, તો પછી x ને અનુક્રમણિકામાંથી દૂર કરો []. અનુક્રમણિકા [એક્સ] = એન.

9. અનુક્રમણિકા એરે સortર્ટ કરો.

આ પણ જુઓ
રોમન માટે પૂર્ણાંક

10. અનુક્રમણિકા [k] એ kth નો પુનરાવર્તિત પાત્ર છે.

અમલીકરણ  

સી ++ પ્રોગ્રામ Kth નો પુનરાવર્તિત અક્ષર શોધવા માટે

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

int main()
{
   string s;
   cin>>s;
   int k;
   cin>>k;
   int n=s.length();
   int count[256];
   int index[256];
   memset(count,0,sizeof(count));
   for(int i=0;i<256;i++)
   {
       index[i]=n;
   }
   for(int i=0;i<n;i++)
   {
        count[s[i]]++;
        if(count[s[i]]==1)
        {
            index[s[i]]=i;
        }
        if(count[s[i]]==2)
        {
            index[s[i]]=n;
        }
   }
   sort(index, index+256);
    if(index[k-1]!=n)
    {
        cout<<s[index[k-1]]<<endl;  
    }
    else
    {
        cout<<-1<<endl;
    }
   return 0;
}

Kth નો રિપીટીંગ કેરેક્ટર શોધવા માટે જાવા પ્રોગ્રામ

import java.util.Arrays;
import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int k=sr.nextInt();
                int n=s.length();
                int freq[] = new int [256];
                int index[] = new int [256];
                for(int i=0;i<256;i++)
                {
                    freq[i]=0;
                    index[i]=n;
                }
                for(int i=0;i<n;i++) 
                {
                    freq[s.charAt(i)]++; 
                    if(freq[s.charAt(i)]==1) 
                    { 
                        index[s.charAt(i)]=i; 
                    } 
                    if(freq[s.charAt(i)]==2) 
                    {
                        index[s.charAt(i)]=n;
                    }
                }
                Arrays.sort(index);
                if(index[k-1]!=n) 
                {
                    System.out.println(s.toCharArray()[index[k-1]]); 
                }
                else
                {
                    System.out.println(-1); 
                }
  } 
} 
tutorialcup
3
i

Kth નોન-રિપીટીંગ કેરેક્ટર શોધવા માટે જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન) જ્યાં n આપેલ એરેનું કદ છે. અહીં આપણે આપેલ શબ્દમાળા "s" ને સરળતાથી પસાર કરીએ છીએ અને દરેક પાત્રની આવર્તનની ગણતરી કરીએ છીએ. તે પછી સતત કામગીરીમાં જરૂરી હોય તેમ કેટલાક કામગીરી કરો.

અવકાશ જટિલતા

ઓ (1) કારણ કે અહીં આપણે ફક્ત ની સતત જગ્યા વાપરીએ છીએ 256 કદ. અહીં આપણે દરેક પાત્રની આવર્તન અને અનુક્રમણિકા સંગ્રહિત કરીએ છીએ.