배열을 두 부분으로 나눕니다. 더 나은 해결책이 필요합니다

Question

1과 0의 배열이 주어지면 첫 번째 배열의 1의 수가 다른 배열의 0의 수와 같도록 배열을 부분으로 나눕니다. 이 파티션이 발생하는 색인을 인쇄하십시오. 그러한 가능성이 많으면 그러한 파티션 중 첫 번째 파티션을 찾으십시오.

여기 예제 코드는 파이썬으로 제공됩니다. 대답은 7입니다. 첫 번째 배열은 a[7]까지입니다. 두 번째 배열은 끝까지 a[8]부터 시작합니다.

이 알고리즘은 정상적으로 작동하지만 복잡성은 O (n^2)라고 생각합니다. 나는 가능한 한 더 나은 해결책을 원한다. 어떤 도움이라도 좋을 것입니다. 디바이더와

def findParts(arr): 
    length=len(arr) 
    count_ones = 0 
    count_zeros = 0 
    index=0 

    for index in range(length-1): 
     if arr[index] == 1: 
      count_ones+=1 
     for j in range(index+1, length-1): 
      if arr[j] == 0: 
       count_zeros+=1 

    if (count_ones-count_zeros == 0): 
     return index 
    else: 
     count_zeros=0; 

a=[1,1,0,0,1,0,0,0,1,0,1,1,0,1,0,1,1] 
print findParts(a) 

Answer 1

다음은 선형 시간 알고리즘 및 용액의 존재 모두에 그 용액을 가능한 유일한 해결책이 증명 :

lst = [1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1] 

index = 0 
leftCount, rightCount = 0, lst.count(0) 
while leftCount < rightCount: 
    if lst[index] == 1: 
     leftCount += 1 
    else: 
     rightCount -= 1 
    index += 1 

print(lst[:index], index, lst[index + 1:]) 

여기

는 코드

인덱스 0에서 시작하여 왼쪽 파티션을 비워두고 왼쪽 파티션 0에서 1의 수를 만듭니다. 우리는 O (n)의 오른쪽 파티션에서 0을 생성합니다.

이제 색인 또는 나누기를 반복하여 오른쪽으로 이동합니다. leftCount가 rightCount보다 여전히 낮 으면 그렇게합니다. 그 점이 바뀌면 우리는 해결책을 찾았습니다 (둘 다 같을 것입니다). 오른쪽으로 이동하면서 list 요소를 살펴 봅니다. 1 인 경우 왼쪽 수에 1을 더합니다. 0 인 경우 올바른 개수에서 하나를 뺍니다. 궁극적으로 우리는 두 지수가 동등한 완벽한 지수에 도달하게 될 것입니다.

각 반복마다 개가 변경되므로 카운트가 항상 개로 변경되므로 항상 이러한 해결 방법이 있습니다. 그리고 반복을 반복하면 균형을 다시 무효화 할 것이므로 이는 솔루션 만있을 수 있다는 증거이기도합니다.

시간 복잡도는 0을 계산하기 위해 목록을 한 번 반복 한 다음 경계를 이동할 때 두 번째로 반복합니다. 그래서 이것은 O (n)입니다.

Answer 2

시작 중앙에 위치하는 요소와 우측 부 (#(0))의 어레이 (#(1))과 0의 총 개수의 왼쪽 부분에서 1 개의 총 수를 계산된다.

#(1) < #(0) 디바이더 한 요소를 오른쪽으로 이동하고 그에 따라 #(0) 및 #(1)을 업데이트하십시오 (이전 디바이더의 값과 새 디바이더의 값을 기준으로 함).

#(1) > #(0) 디바이더 하나의 요소를 왼쪽으로 이동하고 그에 따라 #(0) 및 #(1)을 업데이트하십시오.

O(n)에 분배기가 있습니다.

솔루션의 존재 여부를 미리 확인하여 무한 루프가 발생하지 않도록 할 수 있습니다 (해결 방법이없는 경우, 배열에 0이 모두 1 인 경우).

import math 

def findParts(arr): 
    length = len(arr) 
    index = int(math.ceil(length/2.0)) 
    count_ones = arr[:index+1].count(1) 
    count_zeros = arr[index+1:].count(0) 
    if count_ones == 0 or count_ones == length: 
     return -1 

    while count_ones != count_zeros: 
     if count_ones < count_zeros: 
      index+=1 
      if arr[index] == 1: 
       count_ones+=1 
      else: 
       count_zeros-=1 
     else: 
      if arr[index] == 1: 
       count_ones-=1 
      else: 
       count_zeros+=1 
      index-=1 

    return index 


a=[1,1,0,0,1,0,0,0,1,0,1,1,0,1,0,1,1] 
print findParts(a)