재귀를 사용하지 않고 문자열에서 반복 문자 제거

Question

문자열이 있습니다. 해당 문자열에서 중복 문자를 제거하는 함수를 개발하십시오. 문자열의 길이는 제한 될 수 없습니다. 알고리즘은 공간에 있어야합니다. 원하는 경우 문자열 크기에 관계없이 일정한 크기의 추가 공간을 사용할 수 있습니다. 귀하의 알고리즘은 O (n)의 복잡성을 가져야합니다.

내 생각은 0 번째 색인이 문자 a에 해당하고 25 번째 색인이 z에 해당하며 모든 요소를 ​​0으로 초기화하는 26 크기의 정수 배열을 정의하는 것이 었습니다. 따라서 전체 문자열을 한 번 이동합니다 그리고 우리가 문자를 만날 때와 같이 원하는 색인의 값을 증가시킬 것입니다.

그리고 우리는 다시 한번 문자열을 여행 할 것이고, 원하는 색인의 값이 1이면 우리는 그렇지 않은 문자를 출력 할 것입니다.

이런 식으로 시간 복잡도는 O (n)이고 사용 된 공간은 문자열의 길이에 관계없이 일정합니다 !!

효율성이 더 좋은 아이디어가 있다면 도움이 될 것입니다.

Answer 1

추가 배열 대신 비트 세트를 사용하여 발견 된 문자를 추적 할 수도 있습니다. 허용되는 문자 (a-z 이상)에 따라 적절하게 비트 세트의 크기를 지정하십시오. 정수 배열보다 공간이 적습니다.

Answer 2

귀하의 솔루션은 O (n) 시간 기준에 꼭 맞습니다. 허용 된 알파벳이 큽니다 (유니 코드의 문자 수가 백만자를 초과하는 경우) 매우 큰 배열 대신에 일반 해시를 사용할 수 있습니다. 여기에 (! 최적화되지 않은) 루비의 알고리즘은 다음과 같습니다

def undup(s) 
    seen = Hash.new(0) 
    s.each_char {|c| seen[c] += 1} 
    result = "" 
    s.each_char {|c| result << c if seen[c] == 1} 
    result 
end 

puts(undup "") 
puts(undup "abc") 
puts(undup "Olé") 
puts(undup "asdasjhdfasjhdfasbfdasdfaghsfdahgsdfahgsdfhgt") 

그것은 문자열을 통해 두 개의 패스를 만들고, 해시 조회가 선형 이하이기 때문에, 당신은 좋은거야.

Hashtable (배열과 같이)은 알파벳 크기에 의해 묶여 있기 때문에 큰 공간 임에도 불구하고 상수 공간을 사용한다고 말할 수 있습니다. 알파벳의 크기가 문자열의 크기보다 크더라도 여전히 일정한 공백으로 간주됩니다.

이 문제에는 많은 변형이 있으며 그 중 많은 부분이 재미 있습니다. 진정한 자리를 잡으려면 먼저 정렬 할 수 있습니다. 이것은 O (n log n)을 준다. 병합 중에 dups를 무시한 병합 정렬에는 변형이 있습니다. 실제로이 "외부 해시 테이블 없음"제한은 Algorithm: efficient way to remove duplicate integers from an array (인터뷰 질문 태그 포함)에 나타납니다.

다른 일반적인 인터뷰 질문은 간단한 문자열로 시작됩니다. 그렇다면 지금은 백만 개의 문자열, 이제는 1,000 억 개의 문자가있는 문자열 등입니다. 빅 데이터를 고려하기 시작할 때 상황이 매우 흥미로워집니다.

어쨌든, 당신의 아이디어는 꽤 좋습니다. 일반적으로 다음과 같이 조정할 수 있습니다. 사전이 아닌 집합을 사용하십시오. 골짜기에 가자. 각 문자에 대해 세트에 없으면 추가하십시오. 이 경우 삭제하십시오. 집합은 공간을 적게 차지하고 카운터가 필요 없으며 알파벳이 작 으면 비트 집합으로 구현할 수 있으며이 알고리즘은 두 번 통과 할 필요가 없습니다.

파이썬 구현 : P 모든 프로그래밍 언어의 제약 : http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/