면접 알고리즘?
업데이트 : n에 대한 내 마지막 댓글에 답해주세요. '대명사'm.의 대답?
참고 : 이전에 요청했지만 완전히 엉망이어서 더 자세한 내용과 원본 형식으로 작성하고 있습니다.
질문:
다음과 같은 기능을 지원하고 싶은 N 명의 참가자 (각 1 명부터 N 명까지 인덱싱) 간의 투표 시스템을 관리하고 있습니다.
- Init (N)-데이터 구조를 초기화합니다. -O (1)
- Vote (j, i)-사람 j가 투표 한 (정확히 1) 사람 i에게 투표 한 결과 테이블에 추가합니다. 여기에서 누군가 자신에게 투표 할 수 없습니다. -O (1)
- 유권자 (i)-i에 투표 한 사람 수를 반환합니다. -O (1)
- Origin (j)-j가 다른 사람에게 준 투표 수를 반환합니다. -O (1)
- Favored (k)-상위 참가자가받은 투표 수에 따라 내림차순으로 인쇄합니다. -확인)
- avoided ()-투표를받지 못한 모든 참가자를 인쇄합니다. -O (r) 여기서 r은 인쇄 된 참가자 수입니다.
이 질문에서 공간 복잡성 은 O (N) 이어야합니다 .
배열 및 (더블) 연결 목록 만 사용할 수 있습니다.
제가 한? 크기가 N이고 각 셀에 값이 포함 된 배열을 선언하여 1-4를 쉽게 해결했습니다. got및 sent. 내가 i투표 할 때 j가치를 얻었고 가치 를 1 씩 j보냈습니다 i.
그래도 필요한 복잡성에서 5와 6을 해결하는 방법에 대해 전혀 모릅니다.
참고 : 실제 코드가 아닌 알고리즘 / 아이디어를 찾고 있습니다.
답변
각 작업에 대해 투표 한 후보가 점수를 정확히 1 점 올렸습니다.
이렇게하면 새로운 전략이 열립니다. 후보를 점수에 매핑하는 대신이 점수를 사용하여 후보 목록에 점수를 매핑합니다.
이것은 목록 후보 목록으로 아주 간단하게 구현할 수 있습니다 : (구문과 같은 템플릿에서 :) list<list<Candidate>>.
또한 각 후보 번호를 실제 Candidate요소 의 포인터에 매핑하는 배열을 유지합니다 .
0을 가진 후보 목록은 O (1)에서 배열을 초기화하는 것과 유사한 방식으로 초기에 모든 후보로 암시 적으로 설정됩니다 .
- 투표시 :
- 참조에서 후보를 찾습니다. O (1)
- 현재 목록에서 제거하고 다음 목록에 추가합니다. O (1)
- 지원에
Avoided()에서O(r): "0"리스트의 원소의 개수의 절반보다 작은 경우, 대신 일반 목록으로 변경합니다. - 점수를 나타내는 이전 요소에 이제 후보가없는 경우 드롭하고 이전 점수를 다음 점수에 직접 연결합니다 (즉, 점수가 3 인 후보가 없으면 connect
2<->4). 이렇게하면O(n)빈 목록 노드가 너무 많지 않기 때문에 공간 이 확보됩니다.
O(k)점수 목록을 처음부터 끝까지 반복 (k후보 출력 후 중지)하여 topK를 쉽게 얻을 수 있습니다.- 회피는 지금
O(n) = O(r)의 절반 이상이 후보는 피할 수 있던 경우 또는O(r)삽입에 최적화 (3) 덕분에, 그렇지 않으면.
여기에 avoided ()를 구현하는 다른 방법이 있습니다. 투표를받은 각 사람과 실행 시작 및 실행 종료의 두 번호를 연결합니다. 처음에는 모든 요소가 None(O (1) 배열 초기화 트릭으로 수행 할 수 있음) 로 설정됩니다 .
사람 m이 처음으로 투표 하면 다음을 업데이트 startOfRun하고 endOfRun배열합니다.
if startOfRun[m-1] != None and startOfRun[m+1] == None
endOfRun[startOfRun[m-1]] = m
else if startOfRun[m-1] == None and startOfRun[m+1] != None
startOfRun[endOfRun[m+1]]
else if startOfRun[m-1] != None and startOfRun[m+1] != None
endOfRun[startOfRun[m-1]] = endOfRun[m+1]
startOfRun[endOfRun[m+1]] = startOfRun[m-1]
else
startOfRun[m] = m
endOfRun[m] = m
(간결성을 위해 모서리 조건은 생략 됨).
이제 당신은 투표를받은 사람들의 실행이 있고, 당신은 각 실행의 시작부터 끝까지 쉽게 얻을 수 있습니다. 런 안의 숫자는 모두 틀렸지 만 우리는 그것들에 대해 신경 쓰지 않습니다. O (r) 런이 있으므로 O (r)에서 투표 한 모든 사람을 건너 뛸 수 있습니다.
Favored ()를 구현하는 다른 방법이 있습니다. 두 개의 배열, (1) 점수별로 정렬 된 확장 된 사람 배열 및 (2) 점수보다 낮은 점수를 갖는 첫 번째 배열의 마지막 사람 색인에 대한 점수지도 (해당 사람이 없으면 None) . 처음에 첫 번째 배열은 비어 있고 두 번째 배열은 Nones를 포함 합니다. 예:
(array 1)
(index) 1 2 3 4 5 6 7 8 9
person 3 6 5 1 4 2 8 9 7
score 7 7 7 5 5 3 2 2 2
(array 2)
score 1 2 3 4 5 6 7 8 9
index in 1st 9 9 6 5 5 3 3 - -
한 사람이 처음으로 투표되면 점수가 1 인 배열 끝에 추가되고 array2[1]업데이트됩니다. 그 사람이 다시 투표를 받으면 동일한 점수를 가진 배열의 첫 번째 사람으로 교체되고 점수가 증가하고 두 번째 배열이 업데이트됩니다 (새 항목에 해당하는 요소 하나만 업데이트하면됩니다). 점수).