ค้นหาดัชนี 0 ที่จะแทนที่ด้วย 1 เพื่อรับลำดับต่อเนื่องที่ยาวที่สุดของ 1 วินาทีในอาร์เรย์ไบนารี - Set-2 ใน Python

สมมติว่าเรามีอาร์เรย์ไบนารีหนึ่งอัน เราต้องหาตำแหน่ง 0 ที่สามารถแทนที่ด้วย 1 ได้ เพื่อให้ได้จำนวนสูงสุดของลำดับต่อเนื่องที่ 1 วินาที

ดังนั้น หากอินพุตเป็น [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1] เอาต์พุตจะเป็น 10 ดังนั้นอาร์เรย์จะเป็น [1 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ผม :=0,

• n :=ขนาดของ A

• count_left :=0, count_right :=0

• max_i :=-1, last_i :=-1

• count_max :=0

• ในขณะที่ฉัน

  • ถ้า A[i] เท่ากับ 1 แล้ว

    • count_right :=count_right + 1

  • มิฉะนั้น

    • ถ้า last_i ไม่เหมือนกับ -1 แล้ว

      • ถ้า count_right + count_left + 1> count_max แล้ว

        • count_max :=count_left + count_right + 1

        • max_i :=last_i

    • last_i :=ฉัน

    • count_left :=count_right

    • count_right :=0

  • ผม :=ผม + 1

• ถ้า last_i ไม่เหมือนกับ -1 แล้ว

  • ถ้า count_left + count_right + 1> count_max แล้ว

    • count_max :=count_left + count_right + 1

    • max_i :=last_i

• คืนค่า max_i

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def find_max_one_index(A):
   i = 0
   n = len(A)
   count_left = 0
   count_right = 0
   max_i = -1
   last_i = -1
   count_max = 0
   while i < n:
      if A[i] == 1:
         count_right += 1
      else:
         if last_i != -1:
            if count_right + count_left + 1 > count_max:
               count_max = count_left + count_right + 1
               max_i = last_i
            last_i = i
            count_left = count_right
            count_right = 0
      i += 1
   if last_i != -1:
      if count_left + count_right + 1 > count_max:
         count_max = count_left + count_right + 1
         max_i = last_i
   return max_i
A = [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]
print(find_max_one_index(A))

อินพุต

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

ผลลัพธ์

10