두 개의 스택을 사용하여 큐를 구현했으며 큐의 상위 N % 요소를 찾고 싶습니다. 예를 들어큐의 상위 n 개 요소
는 :
큐는 {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
10 %의 요소 (20) = 2
의 10 %가 이에 대한 답변이
19 20이되어야 수단이 순서대로 요소를 가져 내가 생각할 수있는 두 가지 방법이 있습니다.
이 문제를 해결하는 더 좋은 방법이 있습니까?
큐는 내부의 요소에 액세스하면 안되기 때문에 큐는 최상의 데이터 구조가 아닙니다. 대부분의 큐 구현은 액세스 연산자를 제공하지 않으므로 정렬하지 않아야합니다. 따라서 다른 요구 사항으로 인해 큐가 필요하지 않은 경우 일반 배열을 사용하는 것이 좋습니다.
정렬은 매우 시간이 많이 소요되는 프로세스입니다. 대기열 요소를 읽거나 삽입 할 때 합계를 계산할 수 있습니다. 알려진 합계, 요소 수 및 필요한 비율에 따라 임계 값을 계산할 수 있습니다. 그런 다음 요소를 반복해야합니다 (큐를 사용하는 경우 하나씩 추출 할 수 있음). 계산 된 임계 값보다 큰 큐를 표시 할 수 있습니다.
요소를 정렬 된 상태로 유지하는 다른 데이터 구조를 사용할 수 있습니다. 예를 들어, (tiered vector) 또는 일부 이진 검색 트리를 사용할 수 있습니다.
대부분의 프로그래밍 언어에는 빌드 - 인 RB 트리가 있지만, 실제로는 사용할 수 없습니다. 왼쪽 및 오른쪽 하위 트리의 중요도에 대한 정보를 각 노드에 추가해야합니다.
대기열과 함께 이진 검색 트리/'정렬 집합'을 사용할 수 있습니다.
대기열의 뒤쪽에 요소를 추가 할 때 동시에 그 요소를 집합에 추가합니다. 대기열의 맨 앞에서 요소를 제거하면 해당 요소를 집합에서 동시에 삭제합니다.
대기열에있는 요소의 상위 N %를 찾으려면 다음 요소가 상위 N % 기준에 맞지 않을 때까지 최상위 요소의 집합을 반복 할 수 있습니다. 이는 세트가 대기열에있는 요소의 정렬 된 목록을 유지 보수하기 때문입니다.
또한 원래의 대기열 구조가 계속 존재하기 때문에 대기열에있는 요소의 상대적인 순서를 유지할 수 있습니다.
"두 개의 스택을 사용하여 대기열을 구현했습니다."순전히 기능적 솔루션에 관심이 있습니까? 아니면 그냥 운동입니까? –
이것은 단지 운동에 불과합니다. 알고리즘을 비교 한 아이디어조차도 가능합니다. 위의 두 가지 접근 방식은 O (nlogn)와 O (n)입니다. 둘 다 꽤 빠르다.그러나 나는 그것을 할 수있는 더 나은 방법을 알고 싶습니다 또는 아주 간단하게 이들이 유일한 두 가지 방법이고 내가 선택 알고리즘을 사용해야하는지 여부 –
O (1)에서 MAX를 항상 제공 할 수있는 MAXQUEUE의 일반화를 찾고 있습니까?)? 이 경우 N은 대기열의 주어진 인스턴스에 대한 고정 값입니까? – rici