Python에서 제품이 동일한 두 개의 하위 배열로 배열을 나누는 요소 찾기

<시간/>

크기가 N인 배열이 있다고 가정합니다. 배열을 동일한 곱을 갖는 두 개의 다른 하위 배열로 나누는 요소를 찾아야 합니다. 그러한 파티션이 가능하지 않으면 -1을 반환합니다.

따라서 입력이 [2,5,3,2,5]와 같으면 출력은 3이 되고 하위 배열은 {2, 5} 및 {2, 5}

입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열의 크기
multiply_pref :=새 목록
multiply_pref 끝에 array[0] 삽입
1~n 범위의 i에 대해
- multiply_pref[i-1]*array[i]를 배수의 끝에 삽입
multiply_suff :=크기가 n인 목록, 아무것도 채우지 않음
multiply_suff[n-1] :=배열[n-1]
n-2 ~ -1 범위의 i에 대해 1 감소, do
- multiply_suff[i] :=multiply_suff[i+1]*배열[i]
1에서 n-1 사이의 i에 대해 다음을 수행합니다.
- multiply_pref[i]가multiply_suff[i]와 같으면
  - 반환 배열[i]
반환 -1

예제 코드

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def search_elem(array):
   n = len(array)
   multiply_pref = []
   multiply_pref.append(array[0])
   for i in range(1, n):
      multiply_pref.append(multiply_pref[i-1]*array[i])
   multiply_suff = [None for i in range(0, n)]
   multiply_suff[n-1] = array[n-1]
   for i in range(n-2, -1, -1):
      multiply_suff[i] = multiply_suff[i+1]*array[i]
   for i in range(1, n-1):
      if multiply_pref[i] == multiply_suff[i]:
         return array[i]
   return -1
array = [2,5,3,2,5]
print(search_elem(array))

입력

[2,5,3,2,5]