두 가지 유형의 요소를 포함하는 배열 정렬

두 가지 유형의 요소(예: 1과 0만)만 포함된 배열을 정렬하는 방법에는 여러 가지가 있습니다. 우리는 이 목표를 달성하기 위한 세 가지 방법을 논의할 것입니다. 첫 번째 방법은 미리 정의된 sort() 함수를 사용하여 주어진 배열을 정렬하는 것입니다. 두 번째 방법은 0과 1의 수를 세고 먼저 0의 수를 쓴 다음 1의 수를 써서 배열을 업데이트하는 계산 정렬 방법입니다. 마지막 방법에서는 이중 포인터 방법을 사용했습니다.

문제 설명

1과 0만 포함된 배열이 제공됩니다. 우리의 임무는 1이 배열의 가장 오른쪽에 있고 0이 배열의 왼쪽에 있도록 모든 0과 1을 배열하는 것입니다

Example

의 중국어 번역은

Example

입니다. 으아악

방법 1: 무차별 대입 크래킹 방법.

이 방법에서는 sort() 함수를 사용하여 배열을 직접 정렬해 보겠습니다. 1>0이므로 정렬 후에는 1이 모두 배열의 오른쪽에 배열되고 0이 모두 배열의 왼쪽에 배열됩니다.

Sort() 함수: Sort() 함수는 O(NlogN) 시간이 걸리며 배열을 오름차순으로 반환합니다.

Example

의 중국어 번역은

Example

입니다.

다음은 두 가지 유형의 요소가 포함된 배열을 정렬하기 위한 C++ 구현입니다.

으아악

출력

컴파일되면 위 프로그램은 다음과 같은 출력을 생성합니다.

으아악

방법 2: 개수 정렬 방법

이 방법에서는 단순히 배열에서 0과 1의 수를 세고 배열의 시작 부분에 0을, 끝 부분에 1을 업데이트합니다.

이렇게 하면 배열의 가장 왼쪽 부분에 모두 0이 있고 배열의 가장 오른쪽 부분에 모두 1이 있게 되어 원하는 정렬된 배열을 자동으로 나타냅니다.

간단한 방법이지만 단순히 위치만 바꾸는 것이 아니라 배열에 새로운 값을 삽입하는 방식이므로 효율적이지 않습니다.

Example

의 중국어 번역은

Example

입니다.

다음은 위 메소드를 C++를 사용하여 구현한 것입니다.

으아악

출력

컴파일하면 다음과 같은 출력이 생성됩니다.

으아악

Time Complexity - 하나의 루프만 사용했기 때문에 이 방법의 시간 복잡도는 O(N)

입니다.

공간 복잡성 - O(1). 추가 변수를 사용하더라도 선형이므로 공간 복잡도는 일정합니다.

방법 3: 이 문제를 해결하는 가장 좋은 방법

이 방법에서는 시작과 끝이라는 두 개의 포인터를 유지합니다. 시작 포인터를 사용하여 배열의 시작 부분(인덱스 0)에서 동시에 탐색하고 끝 포인터를 사용하여 끝(인덱스 len-1)에서 탐색합니다.

우리의 임무는 모든 1을 배열의 가장 오른쪽에 배열하는 것입니다. 그러면 자동으로 모든 0이 배열의 왼쪽에 배열됩니다.

초기 인덱스부터 시작하여 찾은 요소가 1이면 인덱스 "end"에 있는 요소와 교체하고 끝 포인터를 1씩 감소시킵니다.

찾은 요소가 0이면 이미 가장 왼쪽 위치에 있기 때문에 스왑 작업을 수행할 필요가 없습니다. 시작 포인터를 1씩 늘리면 됩니다.

Example

의 중국어 번역은

Example

입니다.

이 방법을 구현하는 코드는 다음과 같습니다. -

으아악

출력

으아악

Time Complexity - 배열을 한 번만 반복하므로 이 접근 방식의 시간 복잡도는 선형입니다. 즉, O(N)

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

결론

이 글에서는 두 가지 유형의 요소, 즉 1과 0만 포함된 배열을 정렬하는 세 가지 방법을 논의했습니다.

위 내용은 두 가지 유형의 요소를 포함하는 배열 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!