Kth Təkrarlanmayan Xarakter

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Bloomberg Facebook Goldman Sachs google microsoft Kahin Zillow
Sükut Hashing HashMap SimBaxılıb 247

Problem bəyanat

“Kth-nin təkrarlanmayan xarakteri” ndə a sim "S". Kth-in təkrarlanmayan xarakterini tapmaq üçün bir proqram yazın. Sətirdə təkrarlanmayan k-dan az simvol varsa, “-1” yazdırın.

Giriş Formatı

"S" simli olan ilk və yalnız bir sətir.

Çıxış formatı

K-ni təkrarlayan olmayan xarakteri təmsil edən a_character olan ilk və yalnız bir sətir. Sətirdə təkrarlanmayan k-dan az simvol varsa, “-1” yazdırın.

misal

tutorialcup
3
i

Explanation: Burada freq [t] 2, freq [u] 2 və digər char-ın qalan hissəsi frekadır 1. Beləliklə, Kth təkrarlanmayan xarakterdir "və ya".

Alqoritm

1. Simvol sayını massivdə saxlamaq üçün bir sayma massivi yaradın.

2. Təkrarlanmayan simvollar indeksini saxlamaq üçün indeks seriyası yaradın.

3. Bir dizin 'x' işarəsi təkrarlanırsa və ya indeks dizisindəki n mağazasında yoxdursa.

4. Sayı sıfırla və n ilə indeks massivi başlayın. (n simli uzunluqdur)

5. X = str [i] giriş sətrini keçin

6. Artım sayı [x]

7. [X] = 1 sayılırsa, x indeksini [x] indeksində saxlayın. indeks [x] = i

8. [X] = 2 sayılırsa, x-ı [] indeksindən çıxarın. İndeks [x] = n.

9. İndeks dizisini sıralayın.

10. İndeks [k] təkrarlanmayan k-ci xarakterdir.

Həyata keçirilməsi

K + Təkrarlanmayan Xarakteri tapmaq üçün C ++ proqramı

#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-in təkrarlanmayan xarakterini tapmaq üçün Java proqramı

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-in təkrarlanmayan xarakterini tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür. Burada sadəcə verilən “s” sətrini keçirik və hər bir simvolun tezliyini hesablayırıq. Bundan sonra daimi bir müddətdə tələb olunduğu kimi bir əməliyyat həyata keçirin.

Kosmik Mürəkkəblik

O (1) çünki burada yalnız -ın daimi boşluğundan istifadə edirik 256 ölçüləri. Burada hər bir simvolun tezliyini və indeksini saxlayırıq.

Translate »