[면접] 알고리즘 (2) - 첫 번 째 에 한 번 나타 나 는 문자 (첫 번 째 에 k 번 나타 나 고 가장 많이 나타 나 는 문자)

알고리즘 + 알고리즘 의 시간 복잡 도 분석: = 알고리즘
제목: 문자열 에서 첫 번 째 로 한 번 만 나타 나 는 문 자 를 찾 습 니 다."abaccdeff" 를 입력 하면 "b" 를 출력 합 니 다.
가장 직관 적 인 생각 은 이 문자열 의 모든 문 자 를 처음부터 끝까지 스 캔 하 는 것 이다. 특정한 문자 에 접근 할 때 이 문 자 를 뒤의 모든 문자 와 비교 하 는 것 이다. 만약 에 뒤에서 중복 되 는 문 자 를 발견 하지 못 하면 이 문 자 는 한 번 만 나타 나 는 문자 이다.
글 의 첫머리 에서 말 한 바 와 같이 알고리즘 은 단독으로 알고리즘 을 구성 하지 않 고 그 시간 복잡 도 분석 과 함께 공동으로 알고리즘 을 구성한다.
만약 에 문자열 에 n 개의 문자 가 있 고 i 의 문자 가 있 으 면 뒤의 n - i 문자 와 비교 해 야 한다. 분명히 이때 의 시간 복잡 도 는 O (n2) 이 고 면접 관 은 이런 생각 에 만족 하지 않 을 것 이다.
제목 은 문자 가 나타 나 는 횟수 와 관련 이 있 기 때문에 모든 문자 가 이 문자열 에 나타 나 는 횟수 를 통계 할 수 있 습 니까?(횟수 통 계 는 시간 복잡 도가 O (n) 인 일이 다).이 목적 을 달성 하려 면 모든 문자 의 출현 횟수 를 저장 하기 위해 데이터 용기 가 필요 합 니 다.이 데이터 용기 에서 문자 에 따라 나타 나 는 횟수 를 찾 을 수 있 습 니 다. 즉, 이 용기 의 역할 은 하나의 문 자 를 하나의 숫자 (문자열 에 나타 나 는 횟수) 로 표시 하 는 것 입 니 다. 자주 사용 하 는 데이터 용기 에서 해시 표 는 바로 이 용도 입 니 다.
이 문 제 를 해결 하기 위해 서, 우 리 는 해시 표 의 키 (Key) 를 문자 로 정의 할 수 있 으 며, 값 (Value) 은 이 문자 가 나타 나 는 횟수 를 정의 할 수 있 습 니 다.동시에 우 리 는 문자열 을 두 번 더 스 캔 해 야 한다.

(1) 첫 번 째 스 캔 문자열 은 모든 문자 의 통계 수 를 만 들 기 위 한 것 이 고 표를 만 들 기 위 한 것 이다.

(2) 두 번 째 스 캔 은 횟수 가 요구 에 부합 되 는 문 자 를 찾 아 되 돌아 오기 위 한 것 이다. 즉, 표를 찾기 위 한 것 이다.

해시 표 는 비교적 복잡 한 데이터 구조 이 고 C + + 의 표준 템 플 릿 라 이브 러 리 (STL) 에서 해시 표 가 실현 되 지 않 았 다.다음 에 우리 가 고려 해 야 할 문 제 는 어떻게 해시 표를 실현 하 느 냐 하 는 것 이다.이 문제 의 특성 상 우 리 는 아주 간단 한 해시 표 하나만 있 으 면 수 요 를 만족 시 킬 수 있다.문자 (char) 는 길이 가 8 인 데이터 형식 이기 때문에 모두 256 가지 가 가능 합 니 다.그래서 우 리 는 길이 가 256 인 배열 을 만 들 었 습 니 다. 모든 자 모 는 ASCII 코드 값 에 따라 배열 의 아래 표 시 된 배열 에 대응 하 는 숫자 이 고 배열 에 저 장 된 것 은 모든 문자 가 나타 나 는 횟수 입 니 다.이렇게 해서 우 리 는 크기 가 256 이 고 문자 ASCII 코드 (형식 변환) 를 키 로 하 는 해시 표를 만 들 었 다.

char FirstNotRepeatingChar(char* pStr)
{
    if (pStr == NULL)
        return '\0';
    unsigned int hashTable[256] = {0};
    char* pHashStr = pStr;
    while (*pHashStr != '\0')
        ++hashTable[*pHashStr++];
    pHashStr = pStr;
    while (*pHashStr != '\0')
    {
        if (hashTable[*pHashStr] == 1)
            return *pHashStr;
        ++pHashStr;
    }
    return '\0';
}

하 나 를 들 면 열 을 안다
아래 의 두 가지 문 제 는 주로 두 번 째 스 캔 (즉, 표를 검사 하 는 과정) 을 바 꾸 었 다.

(1) 첫 번 째 로 두 번 나타 난 문자 와 k 번 나타 난 문자

while (*pHashStr == k)
    ...

(2) 가장 많은 문자

unsigned int maxTimes = 0;
char maxTimesChar = '\0';

while (*pHashStr != '\0')
{
    if (maxTimes < hashTable[*pHashStr])
    {
        maxTimes = hashTable[*pHashTable];
        maxTimesChar = *pHashTable;
    }
    ++pHashTable;
}
return maxTimesChar;