데이터 구조에 대한 퍼즐

Question

코딩 경쟁에서이 puzzle 질문 [related to data structure]에 직면했습니다.

나무의 행성이 있습니다 (실제 나무는 나무 데이터 구조가 아닙니다 !!). 수십억 그루의 나무가 있습니다. 임금은 탄소 연대 측정을 사용하여 모든 나무의 연령대 (년 및 정수)의 중앙값을 찾도록 명령합니다. (Method does not matter.) 참고 : 중앙값은 정렬 된 숫자 목록의 "중간 숫자"입니다.

제약은 :
1. 가장 오래된 나무 2000 살 것으로 알려져있다.
2. 그들은 무한대부터 + 무한대까지의 정수를 저장할 수있는 단일 기계를 가지고 있습니다.
3. 그러나 한 번에 메모리에 저장할 수있는 정수의 수는 1 백만 개입니다.

그래서, 다음에 저장하기 위해 100 만 개의 정수를 저장하면 이미 저장된 정수를 삭제해야합니다.
어쨌든 그들은 나무의 나이를 세면서 가면서 중앙값을 추적해야합니다.
어떻게 할 수 있습니까?

내 접근
를 사용하여 외부 종류의 변종은 파일에 쓰기 & 덩어리의 나이를 정렬합니다.
k-way 병합 적용 [청크 용].
위 접근법의 문제점은 파일을 두 번 스캔해야한다는 것입니다. 나는 The oldest tree is known to be 2000 years old.
우리가 count array [as range of ages of tree is fixed] 걸릴 수 없습니다 정보를 사용 다른 접근 방식의

생각 할 수 있습니까?

알고 싶습니다. 더 좋은 방법이 있습니까?
우리가 파일에 데이터를 저장하는 데 필요하지 않는 방법이 존재 하는가? [where only main memory is sufficient?]

Answer 1

당신은 단지 2,001 정수를 저장하여이 작업을 수행 할 수 있습니다. 그런 다음 중간이 사소한 계산 나무에게

ages[thisAge]++ 

을 계산 할 때 다른 가능한 연령대

ages[2001] // [0..2000] 

의 배열을 만듭니다. 두 번째 접근법에서이 솔루션을 사용한 것 같습니다. 그렇다면 을 말하고 싶습니다. 더 좋은 방법이 있습니까? 우리가 에서 파일을 데이터를 저장할 필요가없는 경우

어떤 방법이 존재 하는가? [단지 메인 메모리가 충분 어디?]

당신이 물어 왜 undertstand하지 않는이 메인 메모리가 충분한 방법이 존재한다. 메인 메모리에 2001 년 정수 배열이 맞지 않습니까?

위의 방법을 사용하면 카운트 배열을 채우고 카운트 반복을 통해 중앙값을 계산할 수 있습니다. 합계가 나무의 총 수의 절반에 이르면 중간 값을가집니다. 이를 위해서는 모든 나무를 한 번 통과해야하며 숫자 배열 < = 2001의 부분을 통과해야합니다. 그래서 이것은 O (n)입니다. 대신에이 배열을 사용하여 중앙값을 추적 할 수는 있지만 솔루션에서 실제로 향상되지는 않습니다.

Answer 2

권장 방식 (2001 년 배열)은 O (n)이며 트리마다 하나의 빠른 연산이 있으므로 최적입니다.

음, 거의 최적입니다. 계산 중 어느 시점에서 잔여 나무의 수가 결과를 변경하기에 충분하지 않습니다. 예를 들어, 내가 나무의 반 + 1을 세고 모두 정확히 100 세가된다면 나는 100 년이라는 대답을 얻습니다.

그러나 나무가 잘 흩어져 있으면 필요한 나무 수가 총 수에 가까워집니다.