สมมติว่าเรามีข้อมูลอาร์เรย์แบบไบนารี เราต้องหาจำนวนสวอปขั้นต่ำที่จำเป็นในการจัดกลุ่ม 1 รายการที่จัดเก็บไว้ในอาร์เรย์ร่วมกันในตำแหน่งใดก็ได้ในอาร์เรย์ ดังนั้นหากอาร์เรย์เป็นเหมือน [1,0,1,0,1,0,0,1,1,0,1] ผลลัพธ์จะเป็น 3 วิธีแก้ปัญหาที่เป็นไปได้คือ [0,0,0,0, 0,1,1,1,1,1,1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตั้งค่าหนึ่ง :=0, n:=ความยาวของอาร์เรย์ข้อมูล
- สร้างผลรวมอาร์เรย์ของขนาด n และเติมค่านี้ด้วย 0, set summ[0] :=data[0]
- หนึ่ง :=หนึ่ง + ข้อมูล[0]
- สำหรับ i ในช่วง 1 ถึง n – 1
- summ[i] :=summ[i - 1] + data[i]
- หนึ่ง :=หนึ่ง + data[i]
- แทน :=หนึ่ง
- ซ้าย :=0, ขวา :=หนึ่ง – 1
- ขณะขวา
- ถ้าเหลือ 0 แล้ว temp :=summ[right] หรือ temp :=summ[right] – summ[left - 1]
- ans :=ขั้นต่ำของ ans หนึ่ง – ชั่วคราว
- เพิ่มขวาและซ้าย 1
ตัวอย่าง(Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
