Duplicate Zeros ใน Python

ให้อาร์เรย์จำนวนเต็มความยาวคงที่ ต้อง duplicate ทุกศูนย์ (0) โดยเลื่อนสมาชิกที่เหลือไปขวา สมาชิกที่เกินความยาวเดิมจะถูกตัดทิ้ง

ตัวอย่าง: [1,0,2,3,0,4,5,0] → [1,0,0,2,3,0,0,4] (0 ตัวที่ 3 และ 6 ถูก duplicate ตัวสุดท้ายถูกตัด)

ขั้นตอนการแก้ปัญหา

1. คัดลอกอาร์เรย์ต้นฉบับเป็น arr2 ตั้ง i = 0, j = 0
2. วนลูป while i < len(arr):
   • ถ้า arr2[j] == 0:
     • arr[i] = 0
     • i += 1
     • ถ้า i < len(arr) ให้ arr[i] = 0 (duplicate)
   • มิฉะนั้น arr[i] = arr2[j]
   • i += 1, j += 1

ตัวอย่างโค้ด

class Solution(object):
    def duplicateZeros(self, arr):
        arr2 = [i for i in arr]
        i = 0
        j = 0
        while i < len(arr):
            if not arr2[j]:
                arr[i] = 0
                i += 1
                if i < len(arr):
                    arr[i] = 0
            else:
                arr[i] = arr2[j]
            j += 1
            i += 1
        return arr

ob1 = Solution()
print(ob1.duplicateZeros([1,0,2,3,0,4,5,0]))

อินพุต

[1,0,2,3,0,4,5,0]

เอาต์พุต

[1,0,0,2,3,0,0,4]

วิธีแก้แบบ Two-pass (ในที่เดียว In-place)

def duplicateZeros(arr):
    n = len(arr)
    zeros = arr.count(0)
    # Pass 1: หาตำแหน่งสุดท้ายที่จะเขียน
    i = n - 1
    j = n - 1 + zeros
    while i < j:
        if j < n:
            arr[j] = arr[i]
        if arr[i] == 0:
            j -= 1
            if j < n:
                arr[j] = 0
        i -= 1
        j -= 1