연결리스트에서 가장 자주 나타나는 문자

단일 연결된 문자 목록이 주어지고, 우리의 임무는 연결된 목록에 가장 자주 나타나는 문자를 인쇄하는 것입니다. 여러 문자가 동일한 횟수만큼 나타나면 해당 문자의 마지막 발생이 인쇄됩니다.

단일 연결 리스트는 노드로 구성된 선형 데이터 구조입니다. 각 노드에는 데이터와 다음 노드에 대한 포인터가 포함되어 있는데, 각 노드에 할당된 메모리는 연속적이지 않기 때문에 다음 노드의 메모리 주소를 포함합니다.

예

캐릭터 링크 목록이 주어졌다고 가정해보세요

예 1

입력: LL = a -> b -> c -> c -> c

출력: 가장 일반적인 문자는 c입니다.

설명: 주어진 연결 리스트 LL에서 a는 한 번 나타나고, b는 한 번 나타나고, c는 3번 나타납니다. 따라서 출력은 c입니다.

예 2

입력:

LL = x -> x -> y -> y -> z -> z

출력: 가장 많이 나타나는 문자는 z입니다.

설명: 주어진 연결 리스트 LL에서 x는 2번, y는 2번, z는 2번 나타납니다. z가 마지막에 나타나므로 모든 발생은 동일하므로 출력은 z입니다.

여기에서는 두 가지 방법에 대해 논의하겠습니다. 아래 부분을 살펴보도록 하겠습니다 -

방법 1: 반복적으로 빈도 계산

이 방법의 아이디어는 연결된 목록을 순회하여 각 문자의 빈도를 계산한 다음 빈도가 가장 높은 문자를 찾고, 여러 문자의 빈도가 동일한 경우 해당 문자를 인쇄하고 마지막 문자를 반환하는 것입니다. .

예

으아아아

출력

으아아아

시간 복잡도

: O(N*N), 여기서 N은 연결 목록의 크기입니다.

공간 복잡도: O(1)

방법 2: 계산 배열 사용

이 방법의 아이디어는 각 문자의 빈도를 저장한 다음 배열을 반복하여 가장 높은 빈도의 문자를 찾는 카운트 배열을 유지하는 것입니다. 여러 문자의 빈도가 동일한 경우 해당 문자를 인쇄한 다음 마지막 문자를 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도

O(N), 여기서 N은 연결 목록의 크기입니다.

공간 복잡도: O(N), 여기서 N은 연결 목록의 크기입니다.

결론

여기에서는 연결 목록에서 가장 자주 사용되는 문자를 찾는 방법에 대해 설명합니다. 최대 문자 발생을 찾기 위해 두 가지 방법을 논의했습니다. 첫 번째 방법은 주어진 연결 목록의 각 문자에 대해 while 루프를 사용하고 두 번째 방법은 각 소문자에 대해 for 루프를 사용하고 개수를 유지합니다.

위 내용은 연결리스트에서 가장 자주 나타나는 문자의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!