동일한 문자열을 그룹화하는 가장 좋은 알고리즘은 무엇입니까?

Question

각 정렬 알고리즘이 작업이지만 OVERKILL입니다. 같은 입력의

:

aa 
aa 
cc 
cc 
bb 
bb 
dd 

필요하지 않습니다 각 패턴의 순서 :

aa 
cc 
aa 
bb 
dd 
bb 
cc 

난 그냥 뭔가를해야합니다.

이러한 종류의 작업을위한 알고리즘이 있습니까?

Answer 1

, 또는. 입력 값을 반복하고 값 (태그가 있으면 원하는 경우)이있는 해시 테이블에 을 추가하거나 아직 해시 테이블에 존재하는 경우 1 씩 증가시킵니다.

따라서 알고리듬은 시간과 공간 모두에서 O (n)이며 이는 합리적으로 기대할 수있는 수준입니다. 알고리즘 및 소프트웨어 디자인의 모든 장소에 나타나는 매우 유용한 데이터 구조이므로 해시 테이블에 대해 읽어 보는 것이 좋습니다.

Answer 2

글쎄, 내 머리 꼭대기에서 당신은 각 요소가 몇 개인지를 계산하고 순서대로 게시 된 새 배열을 만드는 패스를 실행할 수 있습니다. 그것은 O (n)이지만 "in-place"는 아닙니다. 따라서

:

// Make outputArrayCounter 
// While inputArray has elements left: 
// if current element is new, add to outputArrayCounter 
// if current element has been seen before, increment a counter associated with that 
// element. 
// Part 2... 
// Make outputArray 
// create the appropriate number of elements as found in the outputArrayCounter for 
// every different element type. 

은 이제 예를 봅시다 :

우리는 aa bb aa cc cc dd cc의 원래의 입력을 가지고있다.

카운터 장치를 만들고 입력을 스캔합니다. aa의 경우 첫 번째 요소가 읽히고 전에는 aa이 발생하지 않았으므로이를 카운터 장치에 추가합니다.

카운터 장치 : [(aa, 1)]

이제 다음 입력, bb을 읽고 계속하자. 또한 발견되지 않고 추가된다

카운터 장치 [(aa, 1), (bb, 1)]

단계 다시 세 번째 요소로 aa을 읽었다. 이것은 우리의 장치에서 발견된다, 그래서 대신에 다시 추가, 우리는 1

카운터 장치에 의해 aa와 관련된 카운터를 증가 : [(aa, 2), (bb, 1)]

나는 계속 당신에게 마지막 카운터 장치 상태를 줄 것이다 :

[(aa, 2), (bb, 1), (cc, 3), (dd, 1)]

이제 우리는 장치를 통해 이동하고 같은 이름의 각 요소에 여러 번 함께 각 요소의 번호를 인쇄 할 수 있습니다. (순서가 중요하다면 관련 셋트 딕셔너리를 사용할지 아니면 주문을 저장하는 일종의 듀플 어레이 장치를 사용할지를 결정하는 구현 세부 사항입니다. 이것은 언어마다 다르지만 그 점을 이해할 수있을 것이라고 확신합니다. 더 추상적으로 associative array 당신은 여기에서 언급 할 수와 나는 해결책을 설명 할 것이다.) 당신은 단순히 여기에 hashtable를 사용하려면

print aa aa bb cc cc cc dd