Кт карактер што не се повторува  


Ниво на тешкотија Лесно
Често прашувано во Амазон Јаболко Блумберг Facebook Голдман Сакс Google Мајкрософт Oracle Zillow
Хаш Хашинг HashMap Стринг

Изјава за проблем  

Во „Kth не-повторувачки карактер“ дадовме a низа „И“. Напишете програма за да го откриете карактерот што не се повторува. Ако има помалку од k карактер што не се повторува во низата, тогаш отпечатете „-1“.

Формат на влез  

Првата и единствената линија што содржи низа „s“.

Формат на излез  

Првата и единствената линија што содржи a_ карактер што го претставува карактерот што не се повторува. Ако има помалку од k карактер што не се повторува во низата, тогаш отпечатете „-1“.

пример  

tutorialcup
3
i

објаснување: Тука freq [t] е 2, freq [u] е 2, а остатокот од другиот карактер има freq 1. Значи, карактерот Kth што не се повторува е „или“.

Алгоритам  

1. Создадете низа за броење за да го зачувате бројот на знаци во низата.

2. Создадете низа индекс за да го зачувате индексот на знаци што не се повторуваат.

3. Ако карактерот 'x' се повторува или не е присутен во стринг-продавницата n во низата индекс.

4. Иницијализирајте ја низата со броење со нули и индексната низа со n. (n е должината на низата)

5. Помина низ влезната низа x = стр [i]

6. Зголемување на бројот [x]

7. Ако брои [x] = 1, тогаш зачувајте го индексот на x во индексот [x]. индекс [x] = i

8. Ако брои [x] = 2, тогаш отстранете го x од индексот []. Индекс [x] = n.

9. Подреди ја низата индекс.

10. Индекс [k] е kth не-повторувачки карактер.

Видете исто така
Цел број на римски

Имплементација  

Програма C ++ за пронаоѓање на карактерот 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 големини Тука ги чуваме фреквенцијата и индексот на секој карактер.