Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 모든 1을 함께 그룹화하기 위한 최소 스왑


바이너리 배열 데이터가 있다고 가정하면 배열에 저장된 모든 1을 배열의 어느 위치에서든 함께 그룹화하는 데 필요한 최소 스왑 수를 찾아야 합니다. 따라서 배열이 [1,0,1,0,1,0,0,1,1,0,1]과 같은 경우 가능한 솔루션은 [0,0,0,0, 0,1,1,1,1,1,1]

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

  • 1:=0, n:=데이터 배열의 길이로 설정
  • 크기가 n인 배열 합계를 만들고 이를 0으로 채우고 summ[0] :=data[0]으로 설정
  • 하나 :=하나 + 데이터[0]
  • 1 ~ n – 1 범위의 i에 대해
    • sum[i] :=summ[i - 1] + 데이터[i]
    • 하나 :=하나 + 데이터[i]
  • an :=하나
  • 왼쪽 :=0, 오른쪽 :=1 – 1
  • 오른쪽
  • left가 0이면 temp :=summ[right], 그렇지 않으면 temp :=summ[right] – summ[left - 1]
  • ans :=ans의 최소값, 1 – temp
  • 오른쪽과 왼쪽을 1씩 증가
  • 반환
  • 예제(파이썬)

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

    class Solution(object):
       def minSwaps(self, data):
          one = 0
          n = len(data)
          summ=[0 for i in range(n)]
          summ[0] = data[0]
          one += data[0]
          for i in range(1,n):
             summ[i] += summ[i-1]+data[i]
             one += data[i]
          ans = one
          left = 0
          right = one-1
          while right <n:
             if left == 0:
                temp = summ[right]
             else:
                temp = summ[right] - summ[left-1]
             ans = min(ans,one-temp)
             right+=1
             left+=1
          return ans
    ob = Solution()
    print(ob.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))

    입력

    [1,0,1,0,1,0,0,1,1,0,1]

    출력

    3