이진 배열이 주어지면 정렬하는 데 필요한 최소 인접 스왑 수

정렬된 배열을 얻기 위해 인접한 요소 간에 필요한 교체 수를 최소화하는 데 사용할 수 있는 다양한 방법이 있습니다. 주어진 출력 배열에는 0과 1이라는 두 가지 유형의 요소만 포함됩니다. 이 문제를 해결하는 두 가지 다른 방법을 논의할 것입니다. 첫 번째 솔루션은 0의 수를 저장하기 위해 추가 공간을 사용하는 반면, 두 번째 솔루션은 일정한 공간만 사용합니다.

문제 설명

0과 1이라는 두 요소만 포함하는 배열이 제공됩니다. 우리의 목표는 주어진 이진 배열을 정렬하는 데 필요한 최소 스왑 수를 찾는 것입니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

으아아아

Explanation

의 중국어 번역은

Explanation

입니다. 으아아아

이제 이 문제를 해결하는 간단한 방법을 논의해 보겠습니다.

방법 1

이 방법에서는 0과 1의 총 개수를 계산합니다. 각 1 뒤에 나타나는 0의 개수를 세고 더하면 됩니다. 우리가 알고 있듯이 정렬 후 모든 1은 배열의 맨 오른쪽에 있고 모든 0은 배열의 맨 왼쪽에 있습니다. 이는 배열의 모든 1을 오른쪽의 모든 0으로 바꿔야 함을 의미합니다. 배열의 각 요소에 필요한 스왑 수는 배열의 오른쪽에 나타나는 0의 총 개수입니다. 필요한 스왑 수를 얻기 위해 각 1에 대해 왼쪽에 나타나는 총 0 수를 계속 추가할 것입니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

아래 예에서는 7개의 숫자로 구성된 이진 배열을 만들었습니다. 위의 방법을 사용하여 배열을 정렬하는 데 필요한 최소 인접 스왑 수를 찾습니다.

으아아아

출력

위의 C++ 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.

으아아아

이 접근 방식의 시간 복잡도 - 루프에서 n번 반복하므로 시간 복잡도는 O(n)

입니다.

공간 복잡도 - 0의 수를 저장하기 위해 추가 배열을 사용하므로 이 방법의 공간 복잡도는 O(n)

입니다.

이제 동일한 문제를 해결하기 위한 더 좋고 효율적인 솔루션을 살펴보겠습니다. 우리의 새로운 솔루션은 추가 공간을 차지하지 않으므로 메모리를 절약합니다.

방법 2

이러한 접근 방식에서는 보조 공간을 일정한 공간으로 최소화하겠습니다. 처음부터 배열을 읽는 대신 끝부터 반복하여 만나는 모든 0의 수를 셉니다. 1을 얻으면 해당 1을 정렬된 위치에 배치하는 데 필요한 스왑 수는 그 전에 발생한 0의 수입니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

다음은 위 메서드의 C++ 구현입니다. -

으아아아

출력

위의 C++ 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.

으아아아

이 접근 방식의 시간 복잡도 - 루프에서 n번 반복하므로 시간 복잡도는 O(n)

입니다.

Space Complexity - 추가 공간을 사용하지 않으므로 공간 복잡도는 선형입니다(예: O(1)).

이 글에서는 0과 1만 포함된 배열을 정렬하는 데 필요한 최소 스왑 수를 계산하는 두 가지 방법에 대해 논의했습니다. 첫 번째 접근 방식에서는 추가 배열을 사용하여 각 단계의 솔루션을 저장했지만, 두 번째 접근 방식에서는 일정한 공간에서 수행하여 공간 복잡성이 더 높아졌습니다.

위 내용은 이진 배열이 주어지면 정렬하는 데 필요한 최소 인접 스왑 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!