평균이 주어진 배열의 중앙값을 초과하는 길이 K의 부분 배열을 계산합니다.

"K 길이 하위 배열"이라는 표현은 정확히 K개의 요소가 있는 연속 하위 배열에 적용됩니다. 동적 프로그래밍, 계산 기하학, 데이터 분석과 같은 영역의 다양한 문제를 해결하려면 하위 배열을 마스터하고 사용하는 것이 필수적입니다.

배열 연산 및 통계에서 또 다른 중요한 개념은 중앙값입니다. 배열의 중앙값은 요소를 오름차순으로 정렬했을 때 가운데에 있는 값을 나타냅니다. 요소 개수가 짝수인 경우 중앙값은 두 중심 값의 평균입니다. 중앙값은 평균보다 극단값이나 이상값에 덜 민감하기 때문에 중심 경향의 지속적인 측정값을 구성합니다.

이 문서에서는 주어진 배열에서 평균이 중앙값을 초과하는 K 길이 하위 배열의 수를 결정하는 과제를 연구하려고 합니다. 데이터 세트의 평균과 중앙값 사이의 관계를 이해함으로써 우리는 이 과제를 자세히 조사하고 이를 해결하기 위한 효율적인 기술을 개발할 수 있습니다. 문제 설명을 분석하고, 주요 개념을 검토하고, 배열에 필요한 K 길이 하위 배열의 수를 알고리즘적으로 효율적으로 계산하는 과정에 참여하세요.

문법

배열의 요소를 오름차순으로 정렬합니다.

으아악

정수 벡터를 선언하세요.

으아악

정수 배열 선언

으아악

C++의 기본 for 루프 구문.

으아악

소스 코드 알고리즘

• 입력 배열과 크기를 읽어보세요.

• 주어진 배열의 중앙값을 계산합니다.

• 길이가 K인 각 하위 배열에 대해 평균을 계산합니다.

• 평균과 중앙값을 비교하세요.

• 평균이 중앙값을 초과하는 통계 하위 배열입니다.

방법 1: 무차별 크래킹

방법 1은 평균이 지정된 배열의 중앙값을 초과하는 K 길이 하위 배열의 수를 결정하는 문제에 대한 간단한 솔루션을 구성합니다. 처음에는 입력 배열이 정렬되고 중앙값이 계산됩니다. 그 후, 프로그램은 가능한 모든 K 길이 하위 배열을 반복하고 해당 구성 요소를 집계하여 평균을 계산합니다. 하위 배열의 평균이 중앙값을 초과하면 개수가 증가합니다. 마지막으로 코드는 그러한 하위 배열의 수를 반환합니다.

알고리즘

• 주어진 배열의 중앙값을 계산합니다.

• 가능한 모든 K 길이 하위 배열을 반복합니다.

• 각 하위 배열의 평균을 계산합니다.

• 하위 배열의 평균이 중앙값보다 크면 개수를 늘립니다.

예 1

아래 코드는 이 기사의 앞부분에서 언급한 무차별 접근 방식을 따릅니다. 먼저 입력 배열을 정렬하고 중앙값을 계산합니다. 그런 다음 가능한 모든 K 길이 하위 배열을 반복하고 해당 요소를 합산하여 평균을 계산합니다. 하위 배열의 평균이 중앙값보다 크면 개수가 증가합니다. 마지막으로 코드는 이러한 하위 배열의 개수를 반환합니다.

으아악

출력

으아악

방법 2: 최적화 방법

방법 2는 지정된 배열의 중앙값을 초과하는 평균을 갖는 K 길이 하위 배열의 수를 결정하는 문제에 대한 우아한 솔루션입니다. 먼저 입력 배열을 정렬하고 중앙값을 계산합니다. 그런 다음 각 K 길이 하위 배열의 합계를 결정하는 데 사용되는 접두사 합계 배열을 계산합니다. 이 알고리즘은 가능한 모든 K 길이 하위 배열을 반복하고 접두어 합계 배열을 사용하여 평균을 계산한 후 중앙값과 비교합니다.

하위 배열의 평균이 중앙값을 초과하면 개수가 증가합니다. 마지막으로 프로그램은 그러한 하위 배열의 수를 반환합니다. 이 접근 방식은 접두사 합 배열을 활용하여 각 K 길이 하위 배열의 합을 계산하여 런타임 복잡성을 줄이기 때문에 첫 번째 접근 방식보다 더 효율적입니다.

알고리즘

• 주어진 배열의 중앙값을 계산합니다.

• 접두사와 배열을 계산하세요.

• 가능한 모든 K 길이 하위 배열을 반복합니다.

• 접두사와 배열을 사용하여 평균을 계산합니다.

• 하위 배열의 평균이 중앙값보다 크면 개수를 늘립니다.

예 2

이 알고리즘은 이전에 설명한 최상의 접근 방식을 따릅니다. 접두사 합계 배열을 활용하여 각 K 길이 하위 집합에 대한 집계를 빠르게 계산합니다. 입력 순서가 정렬되고 중앙값이 결정된 후 접두어 합계가 계산됩니다. 그런 다음 프로그램은 모든 K 길이 하위 집합을 반복하고 접두어 합계 배열을 사용하여 평균을 계산한 후 중앙값과 비교합니다. 평균이 중앙값을 초과하면 개수가 증가합니다. 요약하면, 코드는 그러한 하위 집합의 수를 반환합니다.

으아악

출력

으아악

결론

이 기사에서는 C++를 사용하여 평균이 주어진 배열의 중앙값을 초과하는 K 길이 하위 배열을 계산하는 두 가지 방법을 논의했습니다. 첫 번째 방법은 가능한 모든 K 길이 하위 배열을 반복하고 평균을 계산하는 무차별 대입 방법입니다. 두 번째 방법은 접두사와 배열을 사용하여 평균을 보다 효율적으로 계산하는 최적화 방법입니다. 두 코드 모두 제공되며 필요한 하위 배열 수를 찾기 위해 실행할 수 있습니다.

위 내용은 평균이 주어진 배열의 중앙값을 초과하는 길이 K의 부분 배열을 계산합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!