중복 찾기. 각 요소가 1과 N 사이의 정수인 N + 1 요소의 배열이 주어지면 중복을 찾기위한 알고리즘을 작성하십시오. 알고리즘은 선형 시간에 실행해야하며 O (1) 여분의 공간을 사용하고 원래 배열을 수정할 수 없습니다. 힌트 : 포인터를 두배로 늘입니다.Java에서 배열의 컨텍스트에서 포인터 배가는 무엇을 의미합니까?
저는이 문제를 책에서 해결하려고합니다. 이 상황에서 포인터 두배로하는 것은 무엇을 의미합니까? 이 책은 자바를 사용하므로 자바에서 포인터에 대한 개념이 없다고해도 이것이 자바에 적용 할 수 있어야한다고 가정하고 있습니다.
:
http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html
O 귀하의 실제 문제가 (N) 런타임 및 O (1) 공간이 반쯤 약 다루어진다 페이지와 내가 "포인터를 두배로 늘려야한다"고 가정하는 것이 최선의 해결책으로 제안됩니다. 나는 설명은 훨씬 더 철저한 내가 줄 수있는보다으로 사이트를 방문하는 것이 좋습니다 있지만
let i ← n, j ← n
do: i ← A[i], j ← A[A[j]]; until i = j
set j ← n
do: i ← A[i], j ← A[j]; until i = j
return i
: 문제를 해결하기위한 기본적인 의사 코드는 다음과 같이 주어진다.
공식적으로 두 배가되는 포인터를 알 수는 없지만 배열의 각 요소를 카운터와 값으로 사용하면이 문제를 해결할 수 있습니다. 나는 당신이 스스로 알아 내고 싶다고 생각하기 때문에 의도적으로 전체 솔루션을 제공하지는 않습니다.
힌트 : 배열의 모든 숫자는 int이지만 양수입니다. 당신은 N < MAX_INT를 알고 있습니다. 그걸 당신의 이익에 사용할 수 있습니까?
-1 질문에 대답하기보다는 문제를 해결하기 위해. – eggyal