배열 인덱스 알고리즘의 시작과 끝

Question

9 4 4 9 2 2와 같은 정렬되지 않은 배열이 있으면 해당 배열의 각 숫자의 시작 위치와 끝 위치를 알 수있는 효율적인 알고리즘이 필요합니다. 정렬. 예를 들어 위의 배열의 경우 숫자 2는 시작 색인 0과 종료 색인 1을 갖습니다. 숫자 4는 시작 색인 2와 종료 색인 3을 가지며 숫자 9는 시작 색인 인덱스는 4이고 종료 인덱스는 5입니다 (정렬시). 누구든지 효율적인 방법으로이를 수행하는 방법을 알고 있습니까? 먼저 배열을 정렬하지 않고 그것을 할 수있는 방법이 있습니까?

Answer 1

별개의 요소가 10 개 밖에 없다는 사실을 활용할 수 있습니다.

첫째, 제로, 사람의의 보수, 쉽게 시작과 정렬 된 배열에서 각 숫자의 끝 위치를 해결할 수이 카운트에서 등

를 계산 한 번 배열을 반복.

이것은 변형 된 배열을 실제로 채우지 않는다는 것을 제외하면 Counting Sort의 변형입니다.