평균보다 크거나 같음 k가 가장 긴 연속 서브 어레이

Question

N 개의 정수 배열을 고려하십시오. 요소의 평균이 주어진 수 k보다 크거나 같도록 가장 긴 인접한 부분 배열을 찾습니다.

명백한 대답은 O (n^2) 복잡도입니다. 더 잘할 수 있을까요?

Answer 1

O (n) 시간의 모든 값에서 k를 빼서이 문제를 sum> = 0 인 최장 연속 하위 배열로 줄일 수 있습니다. 이제 접두사 금액을 계산하자

index 0  1  2  3  4  5  6 
array   2  -3 3  2  0  -1 
prefix 0  2  -1 2  5  5  4 

지금이 문제는 가장 멀리 떨어져 prefix_right - prefix_left >= 0와 두 개의 인덱스를 찾는 것입니다. 새로운 접두사 - 인덱스 배열을 만들고 접두사, 그리고 나서 인덱스로 정렬 해 봅시다.

index 2  0  1  3  6  4  5 
prefix -1 0  2  2  4  5  5 

우리는 그 다음 각 접두사, 현재의 접두사보다 크거나 같은 접두어 최대 인덱스 오른쪽에서 왼쪽으로 쓸어 계산하기 위해 수행 할 수 있습니다 이제

index 2  0  1  3  6  4  5 
prefix -1 0  2  2  4  5  5 
maxind 6  6  6  6  6  5  5 

가, 가자 원래의 접두사 배열로 돌아갑니다. 각 프리픽스 - 인덱스 쌍에 대해 우리는 새로운 배열에 대해 바이너리 검색을 수행하여 가장 작은 프리픽스> = 현재 프리픽스를 찾습니다. 우리는 바이너리 검색 프리픽스의 maxind에서 현재 프리픽스의 인덱스를 빼서 현재 인덱스에서 시작하는 최상의 시퀀스 길이를 검색합니다. 최대 길이의 시퀀스를 가져옵니다.

이 알고리즘은 정렬 및 n 개의 이진 검색 때문에 O (n log n)입니다.

Answer 2

우리는 O (n) 시간 및 O (n) 공간 복잡도 문제를 해결할 수 있습니다.
나는 순진하고 최적의 접근 방식으로 시도했습니다.
즉, 문제는 두 단계로 이루어집니다.
(1) 각 ar [i]에서 k를 빼고 새 배열의 누적 값을 찾습니다. 새로운 배열을 cumArr []로 호출 할 수 있습니다.
(2) 이제 문제는 j> i와 cumArr [j]> cumArr [i]와 같이 CumArr []에서 max (j-1)를 찾는 문제가됩니다. 이 단계는 유명한 질문이며 많은 장소에서 찾을 수 있습니다. http://codeshare.io/Y1Xc8

쉽게 처리 할 수있는 작은 코너의 경우가있을 수 있습니다 : 여기

가 실행 코드로 세부입니다.
내 생각 친구를 알려주세요.