K 번째 반복되지 않는 문자  


난이도 쉽게
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 페이스북 서비스 골드만 삭스 구글 Microsoft 신탁 Zillow
해시 해싱 해시맵

문제 정책  

“K 번째 반복되지 않는 캐릭터”에서 우리는 "에스". k 번째 non-repeating_character를 찾는 프로그램을 작성하세요. 문자열에 반복되지 않는 문자가 k 개 미만이면 "-1"을 인쇄합니다.

입력 형식  

문자열 "s"를 포함하는 첫 번째 및 유일한 행입니다.

출력 형식  

k 번째 non-repeating_character를 나타내는 a_character를 포함하는 첫 번째 및 유일한 라인입니다. 문자열에 반복되지 않는 문자가 k 개 미만이면 "-1"을 인쇄합니다.

예  

tutorialcup
3
i

설명 : 여기서 freq [t]는 2, freq [u]는 2, 나머지 문자는 freq 1입니다. 따라서 K 번째 non-repeating_character는 "영형".

암호알고리즘  

1. 배열의 문자 수를 저장할 수 배열을 만듭니다.

2. 반복되지 않는 문자의 인덱스를 저장할 인덱스 배열을 만듭니다.

3. 문자 'x'가 반복되거나 인덱스 배열의 문자열 저장소 n에 존재하지 않는 경우.

4. XNUMX으로 카운트 배열을 초기화하고 n으로 인덱스 배열을 초기화합니다. (n은 문자열의 길이)

5. 입력 문자열 탐색 x = str [i]

6. 증가 카운트 [x]

7. count [x] = 1이면 index [x]에 x의 인덱스를 저장합니다. 인덱스 [x] = i

8. count [x] = 2이면 index []에서 x를 제거합니다. 인덱스 [x] = n.

9. 인덱스 배열을 정렬합니다.

참조
정수에서 로마자로

10. Index [k]는 k 번째 반복되지 않는 문자입니다.

실시  

반복되지 않는 K 번째 문자를 찾는 C ++ 프로그램

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

K 번째 비 반복 문자를 찾는 Java 프로그램

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 번째 반복되지 않는 문자를 찾기위한 복잡성 분석  

시간 복잡성

O (N) 어디에 n 주어진 배열의 크기입니다. 여기서 우리는 단순히 주어진 문자열 "s"를 순회하고 각 문자의 빈도를 계산합니다. 그 후 일정한 시간에 필요한 작업을 수행하십시오.

공간 복잡성

O (1) 여기에서는 상수 공간 만 사용하기 때문에 256 크기. 여기에 각 문자의 빈도와 색인을 저장합니다.