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