나는 n 개의 노드로 된 링크 된 목록을 가지고 있는데, k 번째 노드를 삭제하고 그 노드에 요소를 표시하고 싶습니다. n의 값이 비교적 작고 문제의 복잡성이 문제가되지 않는다면 이것은 쉽습니다.링크 된 목록의 10000 번째 노드 삭제하기
문제는 내가 n> = 200000 인 링크 된 목록에 n 개의 노드가 있고 상대적으로 큰 값 (k = 150000)의 노드를 삭제하려고 할 때입니다.
이 문제에 대한 일반적인 해결책은 연결되어있는 전체 목록을 가로 지르고 노드 (솔루션의 복잡도가 O (n) 인 노드)를 삭제하는 것이지만 간단하고 간단한 솔루션이지만 더 많은 시간이 걸립니다. 이 문제에 대한 다른 해결책은 2 개의 포인터를 가질 수 있지만 여전히 최적의 솔루션이 아닙니다.
나는 최적의 솔루션을 찾고 최소의 시간으로 결과를 제공합니다.
희망 사항은 분명합니다. 도움이 필요합니다 ..
액세스가 O (n)가되도록 링크 된 목록이 있습니다. 컨테이너를 변경하거나 보조 컨테이너를 사용하여 직접 액세스 속도를 높이십시오 (공간 복잡성을 높이십시오). 당신은 모든 치료에 대해 O (1) 복잡성을 가진 마술 컨테이너를 발견하지 못할 것입니다.
솔루션을 제공해 주셔서 감사 합니다만 공간의 복잡성을 증가시키는 것은 다른 방법이 없으면 내가 느낀 것입니다. – sushh
O (1)은 아니지만'O (n)'보다 상당히 개선 된'skip-list '를 사용하면'O (log n)'을 확실히 달성 할 수 있습니다. –
표준 링크 된 목록에는 해당 요소에 대한 유일한 참조가 바로 앞에있는 요소에서 발생하므로 목록의 뒷부분에 빠르게 액세스 할 수있는 방법이 없습니다 (추가 포인터 없음).
인덱스가 알려진 요소에 자주 액세스해야한다는 것을 알고 있다면 배열을 사용하는 것이 좋습니다. (질문을 다시 읽었을지라도 이것은 여전히 요소를 삭제하는 데 전혀 도움이되지 않습니다)
해결책에 대해 Matt에게 감사드립니다. 하지만 나는이 주소를 사용하고 각 노드의 크기를 알아 내고 몇 가지 기본적인 작업을 수행하여 목록의 첫 번째 노드 주소를 가지고 있다고 가정합니다. 수학 연산, 링크 된리스트에서 k 번째 노드의 주소를 알 수 있습니까? – sushh
및 요소에 직접 액세스 할 수 있습니까? – sushh
@sushh 아니, 그럴 수 없어. 인접한 메모리 주소에 요소를 저장하는 컨테이너에서만 수행 할 수 있습니다. 목록은 배열과 달리 비 연속 메모리 주소에 저장됩니다. 이것은 후행 요소를 앞으로 옮길 필요가 없기 때문에 삭제 작업을 쉽게 만들어 주며 목록에서 비용이 훨씬 저렴합니다. –
이것은 인터뷰 질문 일 뿐이며 현실적인 시나리오입니까? 나중에, 귀하가 통제 할 수있는 것과 같은 것, 그리고 모든 것이 변경 될 수있는 것과 같은 다른 것들에 대해 더 많은 통찰력을 줄 수 있습니까? –
단독 연결 목록이있는 경우 유일한 선택은 O (n) 솔루션입니다. 더 많은 정보를 추가하기 위해 데이터 구조를 수정할 수 있습니까? 답변 중 하나에 의해 제안 된 것처럼 중간 노드에 대한 참조 목록을 유지하는 것처럼? –