표준 간격 표현에는 일반적으로 짝을 이루는 시작점과 끝점 세트가 포함됩니다. 지정된 각 간격의 오른쪽에서 가장 가깝고 겹치지 않는 간격을 찾는 것이 현재의 딜레마입니다. 이 작업은 현재 간격과 교차하지 않거나 포함하지 않는 다음 간격을 식별하는 작업을 포함하므로 리소스 할당 및 예약과 같은 다양한 애플리케이션에서 매우 중요합니다.
우리가 보여줄 코드 데모의 이해를 돕기 위해, 알고리즘을 살펴보기 전에 먼저 사용할 구문을 살펴보겠습니다.
으아악이 문제를 해결하려면 가장 가까운 겹치지 않는 파트너를 가리키는 인덱스 스택을 유지하면서 역순으로 반복 간격을 중심으로 하는 체계적인 접근 방식이 필요합니다. 제안된 알고리즘이 이 문제를 해결하는 방법에 대한 간단하지만 효과적인 단계는 다음과 같습니다. -
겹치지 않는 범위의 인덱스를 저장하려면 빈 스택을 만드세요.
간격 수와 동일한 크기로 인덱스 벡터를 초기화하고, 겹치지 않는 간격이 발견되지 않았음을 나타내기 위해 -1로 채워집니다.
오른쪽에서 왼쪽으로 간격을 이동합니다.
스택이 비어 있지 않고 현재 간격과 최상위 간격 사이에 단면적이 있는 경우 해당 스택에서 최상위 인덱스를 제거(팝)합니다.
李>정확한 표현을 보장하기 위해 스택이 비어 있으면 현재 간격을 나타내는 벡터에서 인덱스 위치에 -1이 할당됩니다. 이는 오른쪽에 겹치지 않는 간격이 없음을 의미합니다.
이 작업을 시도하기 전에 지정한 스택에 요소가 있는지 확인하는 것이 좋습니다. 그렇지 않으면 오류가 발생합니다. 해당 구조에 하나 이상의 요소가 있음을 확인한 후, 현재 간격의 벡터의 인덱스 값을 우리가 식별한 구조의 최상위 위치에 있는 해당 요소 및 해당 인덱스 정보와 동일하게 설정하여 이를 수행할 수 있습니다. . 작업을 수행하려면 동일한 구조에 포함하세요.
모든 간격이 처리될 때까지 3-7단계를 반복합니다.
인덱스 벡터를 반환합니다.
이 딜레마를 해결하기 위해 두 가지 전략을 살펴보겠습니다.
이 문제를 해결하기 위한 가능한 전략 중 하나는 폭력을 사용하는 것입니다. 기본적으로 이를 위해서는 각 개별 간격을 검사한 다음 교차 옵션이 명확하지 않을 때까지 오른쪽에 있는 모든 간격과 비교해야 합니다. 하지만. 이 방법을 사용하면 O(N^2)의 시간 복잡도가 발생한다는 점은 주목할 가치가 있습니다. 여기서 N은 검사 프로세스에 참여하는 총 간격 수를 나타냅니다.
매우 성공적인 접근 방식 중 하나는 최근 겹치지 않는 간격을 모니터링하는 수단으로 스택을 활용하는 것입니다. 이 전략의 시간 복잡도는 O(N)입니다. 왜냐하면 우리 작업에서는 간격을 한 번만 정독하면 되기 때문입니다.
우리의 탐색 목표는 C++에서 주어진 각 간격의 오른쪽에서 가장 가깝고 겹치지 않는 간격 인덱스의 최적 위치를 찾는 것입니다. 먼저, 구문적 복잡성을 심도 있게 논의하면서 알고리즘을 제안하고 두 가지 잠재적인 솔루션을 제안합니다. 조사의 일환으로 무차별 접근 방식과 스택 기반 최적화 접근 방식이 성공적으로 테스트된 실행 코드에서 어떻게 작동하는지 보여줍니다. 이 방법을 사용하면 특정 세트에 대해 가장 가깝고 겹치지 않는 간격을 쉽게 식별할 수 있습니다.
위 내용은 주어진 각 N 간격의 오른쪽에서 가장 가깝고 겹치지 않는 간격의 인덱스를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
