K-й неповторяющийся символ  


Сложный уровень Легко
Часто спрашивают в Амазонка Apple Bloomberg Facebook Goldman Sachs Google Microsoft Oracle Zillow
Hash хеширования HashMap строка

Постановка задачи  

В «K-ом неповторяющемся символе» мы дали строка «С». Напишите программу, чтобы узнать k-й неповторяющийся_символ. Если в строке меньше k символов, которые не повторяются, выведите «-1».

Формат ввода  

Первая и единственная строка, содержащая строку «s».

Формат вывода  

Первая и единственная строка, содержащая a_character, который представляет k-й неповторяющийся_символ. Если в строке меньше k символов, которые не повторяются, выведите «-1».

Пример  

tutorialcup
3
i

Объяснение: Здесь freq [t] равно 2, freq [u] равно 2, а остальная часть другого символа имеет частоту 1. Таким образом, K-й non-Repeating_character равен «О».

Алгоритм  

1. Создайте массив count для хранения количества символов в массиве.

2. Создайте индексный массив для хранения индекса неповторяющихся символов.

3. Если символ «x» повторяется или отсутствует в строке, сохраните n в массиве индексов.

4. Инициализируйте массив счетчиков нулями и массив индексов с помощью n. (n - длина строки)

5. Пройдите по входной строке x = str [i]

6. Количество приращений [x]

7. Если count [x] = 1, то сохраните индекс x в index [x]. index [x] = i

8. Если count [x] = 2, удалите x из индекса []. Индекс [x] = n.

9. Отсортируйте индексный массив.

Смотрите также
Целое в римское

10). Индекс [k] - это k-й неповторяющийся символ.

Реализация  

Программа на C ++ для поиска K-го неповторяющегося символа

#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;
}

Программа на Java для поиска K-го неповторяющегося символа

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

Анализ сложности для поиска K-го неповторяющегося символа  

Сложность времени

О (п) в котором n размер данного массива. Здесь мы просто просматриваем заданную строку «s» и подсчитываем частоту каждого символа. После этого выполните некоторые операции по мере необходимости в постоянное время.

Космическая сложность

O (1) потому что здесь мы используем только постоянное пространство 256 размеры. Здесь мы храним частоту и индекс каждого символа.