처음 N개의 자연수의 순열을 포함하는 배열 A가 있고 M ≤ N인 다른 숫자 M도 주어진다고 가정하면 다음과 같은 하위 배열의 수를 찾아야 합니다. 시퀀스의 중앙값은 M입니다. 시퀀스의 중앙값은 우리가 알다시피 오름차순으로 정렬한 후 시퀀스의 중간에 있는 요소의 값으로 정의됩니다. 짝수 길이 시퀀스의 경우 두 개의 중간 요소의 왼쪽이 사용됩니다.
따라서 입력이 A =[3, 5, 6, 4, 2] 및 M =5와 같으면 필요한 하위 배열이 [3, 5, 6], [5], [5이므로 출력은 4가 됩니다. , 6] 및 [5, 6, 4].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=arr의 크기
-
my_map :=새 지도
-
my_map[0] :=1
-
has :=False, 추가 :=0, 결과 :=0
-
0에서 n 사이의 i에 대해 수행
-
arr[i]
-
추가 :=추가 - 1
-
-
그렇지 않으면 arr[i]> m일 때
-
추가 :=추가 + 1
-
-
arr[i]가 m과 같으면
-
가 있음 :=참
-
-
has가 참이면
-
my_map에 현재를 추가하면
-
결과 :=결과 + my_map[추가]
-
-
my_map에 add-1이 있으면
-
결과 :=결과 + my_map[추가 - 1]
-
-
-
그렇지 않으면
-
my_map[add] :=(my_map[add]의 값, 존재하는 경우, 그렇지 않으면 0) + 1
-
-
-
반환 결과
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(arr, m):
n = len(arr)
my_map = {}
my_map[0] = 1
has = False
add = 0
result = 0
for i in range(n):
if (arr[i] < m):
add -= 1
elif (arr[i] > m):
add += 1
if (arr[i] == m):
has = True
if (has):
if(add in my_map):
result += my_map[add]
if add-1 in my_map:
result += my_map[add - 1]
else:
my_map[add] = my_map.get(add, 0) + 1
return result
arr = [3, 5, 6, 4, 2]
m = 5
print(solve(arr, m)) 입력
[3, 5, 6, 4, 2] , 5
출력
3