가장 높은 숫자 n 찾으십시오.

수백만 개의 정수가 있습니다. 이것에서 n 개의 가장 큰 숫자를 찾는 방법? 입력이 거대하기 때문에 메모리에 아무 것도 저장할 수 없습니다.가장 높은 숫자 n 찾으십시오.

제안 사항?

덕분에 모든 숫자를 통해

출처

2012-02-13 Shags

'n'의 크기는 얼마나됩니까? 모든 결과를 메모리에 저장하기에 충분합니까? – millimoose

== 가장 큰? – shift66

몇 가지 코드를 보여주십시오. –

당신은 반복 할 수있는 (예를 들어 하나 미디어 하나를 읽기) 만 10 개 최대 번호 목록을 유지 사랑을 나누지 . 의사 코드에서

은 :

max_numbers = new int[n] 
until not end of file: 
    read number 
    if number > min(max_numbers): 
     'copy number to minimum value of max_numbers'

출처

2012-02-13 13:20:22

-1

나는 그것이 논리적 인 결론이다에 마이클의 제안을 고려하여 우선 순위 - 큐 (기반 힙)을 형성하는 것이 좋습니다

을 편집했다. 저장하지 마십시오 10, 상점 n.

PQ a[n]; a.insert(input);

O(log n)은 FTW

출처

2012-02-13 13:20:24

아니요, 힙은 O (N lg n)에 답을 제공합니다. N은 수백만에 해당합니다. 또한이 작업을 수행하려면 [min-heap] (http://stackoverflow.com/a/9118787/166749)이 필요합니다. –

미리 정의 된 최대 깊이 만 갖도록 힙을 수정하지 않았다면 모든 입력을 메모리에 유지해야합니다. 나는 이것이 도움이 되기에는 너무 모호한 위키피디아 링크를 만든다고 주장한다. – millimoose

내 대답이 변경되었습니다. 검토하시기 바랍니다. –

당신이 번호를 통해 실행하면서, 새로운 더 큰 함께 작은 스왑, 10 길이의 배열을 가져옵니다.

출처

2012-02-13 13:23:37 sinsedrix

public void largest() { 
    int _current, _highest, _lowest; 

    if(_current >= _highest) { 
     _highest = _current; 
    } else if(_current <= _lowest) { 
     _lowest = _current; 
    } 
}

나는 무엇을 할 것입니다.

출처

2012-02-13 13:49:24