C++ 프로그램: 연결된 목록의 중복 노드를 복사본으로 교체

이 기사에서는 1부터 n까지의 요소와 중복된 요소가 포함된 연결 목록이 제공됩니다. 1부터 n까지의 요소는 항상 [1..n]에 중복되어 존재합니다. 반복되는 각 요소를 n+1, n+2 등으로 바꿔야 합니다.

예를 들어보겠습니다

1→2→2→4→5→3→6→6

다음 n = 42. 따라서 각 중복은 n+1, n+2 등으로 대체됩니다. 다음 42는 47로 대체되고, 다음 46은 48로 대체되며 첫 번째 인스턴스는 그대로 유지됩니다.

먼저 아래와 같이 메인 메소드에서 이진 트리를 구성해야 합니다. -

으아악

이제 노드는 다음과 같습니다.

1→2→7→4→5→3→6→8

우리가 관찰했듯이 n의 시작 값을 찾으려면 우리가 보는 요소를 추적해야 합니다. 또한 값을 대체하기 위해 반복되는 요소를 결정하는 메커니즘도 필요합니다.

즉시 떠오르는 제안된 데이터 구조를 식별합니다. 연결된 목록을 반복하고 요소를 컬렉션에 푸시할 수 있습니다. 세트의 요소를 푸시한 후에는 세트가 정렬된 데이터 구조이기 때문에 연결 목록에서 사용할 수 있는 가장 큰 요소인 마지막 요소를 찾을 수 있습니다.

연결된 목록의 두 번째 순회에서는 집합을 해시로 사용할 수 있습니다. 우리는 컬렉션의 모든 요소를 ​​검색할 것이며 두 가지 상황이 발생할 수 있습니다.

• 컬렉션에서 요소를 찾아 컬렉션에서 제거하고 표시합니다.

• 세트에서 요소를 찾지 못했습니다. 즉, 이미 옵션 1에서 보았으며 다음 n으로 대체할 예정입니다.

예

링크드 리스트에서 노드를 중복된 값으로 대체하려면 아래 C++ 프로그램을 따르세요. C++ 구현은 컬렉션 데이터 구조를 활용하여 연결된 목록을 탐색하므로 중복 요소 검색이 용이합니다.

으아악

출력

으아악

결론

우리는 해싱 개념을 사용했으며 일련의 데이터 구조의 도움을 받아 연결 목록에서 가장 큰 요소를 찾았습니다. 해시로 map 또는 unordered_map을 사용할 수도 있습니다.

위 내용은 C++ 프로그램: 연결된 목록의 중복 노드를 복사본으로 교체의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!