JavaScript 프로그램: 배열이 정렬되었는지 확인하고 회전합니다.

정렬 배열은 모든 요소가 오름차순으로 배열된 배열입니다. 크기 N의 배열과 고유한 정수를 포함하는 배열이 제공됩니다(각 정수가 한 번만 나타남을 의미). 배열이 시계방향으로 정렬되어 회전되어 있는지 확인해야 합니다. 여기서 배열이 정렬되어 회전되면 "YES"를 반환해야 하고, 그렇지 않으면 "NO"를 반환해야 합니다.

Note - 여기서는 정렬과 회전에 대해 이야기하고 있는데, 이는 적어도 한 번의 회전이 있어야 한다는 의미입니다. 정렬된 배열을 정렬 및 회전된 배열로 처리할 수 없습니다.

N 크기의 배열이 주어졌다고 가정해 보세요

들어가세요

으아악

출력

으아악

지침

Array는 배열로 정렬되어 1비트씩 회전됩니다

으아악

1위치로 정렬하고 회전한 배열이 입력 배열과 일치하므로 출력은 "yes"입니다.

들어가세요

으아악

출력

으아악

지침

주어진 배열은 정렬되지 않고 회전된 배열입니다

으아악

위의 정렬되거나 회전된 배열은 입력 배열과 일치하지 않으므로 대답은 '아니오'입니다.

방법

여기에서는 두 가지 방법에 대해 논의하겠습니다. 아래 섹션에서 살펴보겠습니다 -

방법 1: 피벗 요소(최소 개수)를 찾아 배열이 정렬 및 회전되었는지 확인합니다.

이 방법의 아이디어는 최소 숫자를 찾고 배열이 정렬 및 회전되면 최소 숫자 전후의 값이 정렬된 방식으로 있어야 한다는 것입니다.

예

으아악

시간 복잡도 - O(N), 여기서 N은 배열의 크기입니다.

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

방법 2: 인접 반전을 계산하여 배열이 정렬 및 회전되었는지 확인

이 방법의 아이디어는 배열을 반복하여 이전 요소가 현재 요소보다 작은지 확인하는 것입니다. 정렬 및 회전된 배열의 경우 이전 요소가 현재 요소보다 크면 개수는 1이어야 하며, 그렇지 않으면 배열이 정렬 및 회전되지 않습니다.

예

으아악

시간 복잡도 - O(N), 여기서 N은 배열의 크기입니다.

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

결론

이 튜토리얼에서는 배열이 정렬되고 회전되었는지 확인하는 방법을 논의했습니다. 여기서는 두 가지 방법을 볼 수 있습니다. 첫 번째는 피벗(가장 작은 요소를 의미)을 찾는 것이고, 다른 하나는 인접한 반전을 계산하는 것입니다. 두 방법의 시간 복잡도와 공간 복잡도는 각각 O(N)과 O(1)로 동일합니다.

위 내용은 JavaScript 프로그램: 배열이 정렬되었는지 확인하고 회전합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!