알고리즘 : 마지막 n 개의 고유 번호를 순서대로 기억하십시오.

Question

마지막 n 개의 고유 번호를 순서대로 기억하고 싶습니다. 의 말을하자 N 내가 6을 추가하는 경우 = 4

내 현재 목록이 5 3 4 2, 그것은 3 4 2 6로 바뀝니다 : 여기

무슨 뜻인지입니다. 대신 3을 더하면 목록은 5 4 2 3으로 바뀝니다. 여기서 3은 앞쪽으로 이동합니다.

나는 이렇게 할 것이다 : 대기열에 숫자를 저장하십시오. 새 번호를 추가 할 때 해당 번호의 대기열을 검색하십시오. 번호를 찾지 못하면 끝에있는 번호를 튕겨 앞면에있는 새 번호를 누릅니다. 번호가 발견되면 해당 위치의 번호를 제거한 다음 새 번호를 앞에 밉니다.

분명히 대기열 작업 (예 : C++의 std::deque)에 최적화 된 대기열의 임의 위치에서 숫자를 제거하는 작업은 상당히 느립니다. 연결된 목록을 사용하면 목록을 검색하는 속도가 느려집니다. 이런 종류의 작업을 수행하기 위해 알고리즘 + 데이터 구조의 더 나은 조합이 있습니까?

아무런 차이가 없으면 "마지막 n 개의 고유 번호를 순서대로 기억하고 있습니다." 필자는 특별히 추가시 목록에서 제거 된 요소가 무엇인지 알아야합니다.

Answer 1

이중 연결 목록을 사용할 수 있습니다. n 개의 숫자를 해시 테이블에 추가 할 수 있습니다. 여기서 해시 테이블은 키가 숫자이고 값이 해당 숫자를 포함하는 링크 된 목록의 노드를 가리키는 포인터입니다.

그런 다음 단계에서는 번호가 일정 시간이 아닌 큐를 사용하여 라이너 시간 것이다 해시 테이블 인 경우 룩 변경할 수위한 큐를 통해 검색을 설명한다.

설명하는 pop 및 push 작업은 이중 연결 목록의 첫 번째 요소를 가리키는 포인터 p와 목록의 마지막 요소를 가리키는 포인터 q를 저장하면 일정 시간 내에 수행 할 수 있습니다.

귀하의 단계 숫자가 발견되면 이미 제거 할 숫자의 위치를 ​​가지고 있기 때문에 일정한 시간 내에을 수행 할 수 있습니다. (위치에 따라 나는 해시 테이블).

UPDATE :

은 제거하고 그에 따라 새로운 번호를 추가하여 해시 테이블을 업데이트해야 함을주의하십시오.