파티션을 가진 선택 알고리즘

Question

정수를 배열에 하나씩 입력해야합니다. 입력 과정이 진행되는 동안 숫자의 최상위 (가장 큰) 1/3에서 가장 작은 숫자를 찾도록 요청받을 수 있지만, 여러 번.

예 :

input 1 

input 7 

input 9 

tell the number 

input 21 

input 8 

input 5 

tell the number 

input 11 

tell the number 

출력해야한다 :

9 

9 

11 

설명 :

첫 번째 쿼리까지
• 배열 번호 1 7 9 것, 그래서 상위 1/세번째 숫자는 9. 일 것입니다. 그것들은 단 하나의 숫자이므로 그것도 가장 작습니다.
• 초 쿼리가 정렬 배열 것에 있도록 배열, 1 7 9 21 8 5과 같을 것이다 이루어질 때 : 최종 쿼리
  상위 1/3 숫자가 21이 될 것이다 21 9 8 7 5 1 및 9. 그 의 작은이 될 것입니다 9
• 어레이 (21) 및 이들의 최소 11 것 21 11 9 8 7 5 1 상부 1/3 참조 정렬에 1 7 9 21 8 5 11을 보유하는 제

인 배열 정수의 총 개수가 될 수 250,000

내 접근 파티션과 선택 알고리즘을 적용하는 것입니다하지만 그것은 제한 시간을 초과했습니다.

Answer 1

(나는이 질문은 숙제 어떤 종류의 가정 ("우리는해야한다")와 그에 따라 나는 똑 바르게 답을주고 있지 않다.)

이 당신의 작업을 재구성 : 당신이와 66 백분위 수를 찾을하라는 메시지가 온라인 알고리즘. 012 백 85 번째 백분위 수입니다, 그래서 거기에서 적응할 수 있어야합니다. 그 알고리즘이 좋지 않다면, 온라인 중견 알고리즘에 대한 연구를 수행하십시오. 대부분의 알고리즘은 문제에도 적용되어야합니다.

Answer 2

선택 알고리즘이 실패하는 이유 :
선택 알고리즘을 사용하는 것은 # 요소에서 선형입니다. #elements에서 #requests가 선형이라고 가정하면 이차원 솔루션으로 이어 지므로 시간 제한을 초과하게됩니다.

다른 방법 : 두 추적 유지 : 최대 힙 H1 및 최소 힙 H2

최대 힙 (H1)는 2/3 낮은 수치를 유지되지만 최소 힙 것 금 1/3 가장 높은 숫자. 당신이 상위 1/3 힙 (H2)를 증가해야하는 경우

지금, 읽고 각 요소 x에 대해 확인하고 당신이 할 경우 : 당신은 max{x,H1.max()}를 추가해야합니다. H1.max()을 추가 한 경우 - 힙에서 제거하고 x을 대신 삽입해야합니다. 추가가 필요하지 않은 경우 x이 더 큰 경우 H2.min()인지 확인하고 최소 형식 H2을 제거한 다음 H1에 삽입하고 x을 H1에 추가합니다.

참고 :이 솔루션에서 찾고있는 번호는 언제든지 O(1)에서 찾을 수 있습니다. 최소 힙 (H2)의 최소값입니다.

이 솔루션의 경우 전체 복잡도는 입니다. 여기서 n은 숫자이며, k은 "숫자를 말하십시오"요청의 총 수입니다.

주 : 간단한 해결책은 (아마도 느린하지만) (A BST 또는 예를 들어 skiplist)에 정렬 된 목록을 유지하고 관련 요소를 찾기 위해 이진 검색을 사용하는 것입니다.

예 :

init: 
H1 = {} 
H2 = {} 

input1: 
H1 = {1} 
H2 = {} 

input7: 
H1={1,7} 
H2 = {} 

input 9: //need to add a max, in this case: x > H2.max() -> add x to H2. 
H1 = {1,7} 
H2 = {9} 

tell the number 
H2.min() = 9 

input 21: // 21>9 -> remove H2.min() add it to H1, add x to H2 
H1 = {1,7,9} 
H2 = {21} 

input 8: 
H1 = {1,7,8,9} 
H2 = {21} 

input 5: //remove max from H1, add max to H2, add x to H1 
H1 = {1,7,5,8} 
H2 = {9,21} 

tell the number 
H2.min() = 9 

input 11: //remove min from H2, add it to H1, add x to H2. 
H1 = {1,7,5,8,9} 
H2 = {11,21} 
tell the number 
H2.min() = 11 

에 대해 어떻게

Answer 3

: (N)

1. 하는 정렬 방법으로 배열을 유지, 삽입 비용 = 로그
2. 1/3 중 작은 값을 얻을 = O (1)