아래 문제에 대한 메모리와 시간 효율적인 솔루션을 찾고 있습니다. O (n 2 ) 메모리와 O (n 2 log n) 시간 (?) 을 사용하는 기본 알고리즘은 쉽게 생각할 수 있으며 훨씬 더 많은 메모리와 시간 효율적인 알고리즘이 있는지 알고 싶습니다. (특정 입력 구조의 경우).
입력 : 음이 아닌 정수로 채워진 길이 n의 배열 a. 배열의 각 정수는 b보다 작거나 같은 크기입니다. n은 크고 (수천만), b는 n (수백)에 비해 상대적으로 작은 설정에 관심이 있습니다. a에서 특정 정수의 발생 횟수가 m 이상으로 제한되어 있다고 가정 할 수 있습니다. 여기서 m은 n / b 정도입니다.
배열 a의 모든 회전 집합을 고려합니다. 즉 a = (a 1 , a 2 , ..., a n )이면 해당 회전은 (a 1 , a 2 , ..., a n ), (a 2 , a 3 , ..., a n , a 1 ), (a 3 , a 4 , ..., a n , a 1 , a 2 ), ..., (a n , a 1 , a 2 , ..., a n-1 ). r 1 , r 2 , ..., r n 배열 a 회전의 사전 순으로 정렬 된 (증가) 순서를 나타냅니다 (0 <1 <2 <... <b 사용).
출력 : 두 배열 첫번째 및 마지막으로 그 연구의 성과 저장 소자 (1)는 R, 2 , ..., R , N을 정렬 된 순서에 따라.
기본 알고리즘 (메모리 또는 시간 효율적이 아님) : a의 모든 회전을 구성하고이를 행렬 A (O (n 2 ) 메모리 사용 )에 저장합니다. 정렬 루틴 (표준 정렬 기술 사용)을 정의하여 정렬 A. 정렬 된 행렬의 첫 번째 및 마지막 열을 추출합니다. 아마도 정렬 단계의 가장 좋은 시간 복잡도는 O (n 2 log n), 즉 정렬 알고리즘의 경우 O (n log n)에 각 쌍별 비교에 대해 O (n)을 곱한 것입니다.
두 번째 알고리즘 : 배열을 살펴보고 b보다 작거나 같은 정수 i로 시작하는 위치를 저장할 수 있습니다 (이는 O (n) 시간 및 O (nm) 메모리 연산입니다). 그런 다음 특정 정수 i로 시작하는 모든 회전을 생성하고 기본 알고리즘에 따라이 회전 행렬을 정렬 할 수 있습니다 (이 행렬을 저장하는 것은 O (nm) 메모리를 사용하고 정렬하는 데 아마도 O (mn log m) 시간이 걸립니다). 0에서 b까지의 모든 정수 i에 대해 프로세스를 반복하여 출력을 구성하는 것은 쉽습니다.
맞춤형 정렬 전략을 사용하는보다 메모리 효율적인 접근 방식이 있습니까? 출력을 저장하려면 O (n) 메모리 만 필요하기 때문에 희망적입니다.
O (nlogn)에서 주어진 배열에 대한 접미사 배열 을 계산 합니다. 연결된 구현은 순환 시프트를 정렬합니다 (접미사에 특수 문자가 사용됩니다-필요하지 않음)-정확히 필요한 것 (그러나 물리적 정렬없이 "정렬")
그런 다음 접미사 배열에서 인덱스로 주소가 지정된 초기 배열 요소를 추출합니다. 이것은 시작 요소 목록이 필요합니다 (종료 요소는 이전 인덱스에 있음).
P[0]최소 순환 시프트의 위치가 포함되므로 A[P[0]]과 A[P[0]-1], 제 쌍이다 P[1]- 다음 작은 시프트 등의 총수
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다