배열 고유 한 요소와 모바일 앱 데이터 구조는

Question

질문

1. 당신은 한 번만 발생하는 하나 개의 요소를 제외하고 두 번 반복 모든 요소와 정수의 배열을 부여 인터뷰에서했다 최근 아래에, 당신은을 찾을 필요 O (nlogn) 시간 복잡성을 지닌 고유 한 요소. 배열이 {2,47,2,36,3,47,36}이라면 출력은 3이어야합니다. 나는 우리가 다음 요소를 검사 할 수있는 후에 병합 정렬 (nlogn)을 수행 할 수 있다고 말했지만 그는 O (nlogn) + O (n)을 취할 것이라고 말했다. 또한 HashMap을 사용하여 요소 수를 유지할 수 있다고했지만 다시 결과를 얻으려면 해시 맵을 반복해야하므로 다시 아니라고 말했습니다. 몇 가지 연구를 한 후에 xor 연산을 사용하면 O (n)로 결과를 얻을 수 있다는 것을 알게되었습니다. O (nlogn) 시간에 답변을 줄 수있는 정렬 이외의 더 좋은 해결책이 있습니까?
2. 스마트 폰을 사용할 때마다 한 번에 많은 앱을 열 수 있습니다. 현재 모든 앱이 열려 있는지 살펴보면 최근 열어 본 앱이 맨 앞에 표시되며 목록의 어느 곳에서나 앱을 삭제하거나 닫을 수있는 목록이 표시됩니다. 매우 효율적인 방법으로 모든 작업을 수행 할 수있는 Java에서 사용할 수있는 콜렉션이 있습니다. 우리가 LinkedList 또는 LinkedHashMap을 사용할 수 있다고 말했지만 그는 확신하지 못했습니다. 사용할 수있는 최고의 컬렉션은 무엇입니까? 면접관이 큰-O 표기법을 사용하고 O(n log n) 솔루션을 예상하는 경우

Answer 1

1. 첫째, 당신의 대답 아무 문제가 없습니다. 우리는 그것이 O(x + y) = O(max(x, y))임을 압니다. 따라서 귀하의 알고리즘은 O(n log n + n)이지만 O(n log n)으로 전화하면됩니다. 그러나 이진 탐색을 사용하여 O(log n)에서 정렬 된 배열에 한 번 나타나는 요소를 찾을 수 있습니다. 힌트로 검색을 수행하는 동안 홀수 및 짝수 인덱스를 이용합니다. 또한 면접관이 O(n log n) 해결책을 기대한다면, 횡단에 대한 반대는 터무니 없습니다. 해시 맵 솔루션은 이미 O(n)이며 문제가있는 경우 추가 공간이 필요합니다. 이러한 이유 때문에 언급 한 XOR을 사용하는 것이 가장 좋습니다. 여전히 더 많은 O(n) 솔루션이 있지만 XOR 솔루션보다 우수합니다.
2. 내게는 LinkedList도이 작업에 적합합니다. 우리는 어느 위치에서든 제거하고 싶고 또한 스택 조작 (push, pop, peek)을 사용하기를 원합니다. 맞춤 스택은 LinkedList에서 만들 수 있습니다.