สมมติว่าเรามีอาร์เรย์ A ที่มีตัวเลข n และอินพุต K อื่น เราต้องหาดัชนีสุดท้ายที่จะลดเหลือศูนย์หลังจากดำเนินการตามที่กำหนด อธิบายการดำเนินการดังนี้ −
เริ่มต้นจาก A[0] ถึง A[N – 1] อัปเดตแต่ละองค์ประกอบเป็น A[i] =A[i] – K ตอนนี้ถ้า A[i]
เราต้องทำซ้ำการดำเนินการจนกว่าองค์ประกอบทั้งหมดจะลดลงเป็น 0 และส่งคืนดัชนีซึ่งจะเป็นค่าสุดท้ายที่จะกลายเป็นศูนย์
ดังนั้น หากอินพุตเป็น A =[4, 3, 6, 8, 3, 10] และ K =4 เอาต์พุตจะเป็น 5 เนื่องจากการดำเนินการจะเป็นดังนี้ − Operation 1 − A ={0, 0, 2 , 4, 0, 6} การดำเนินการ 2 − A ={0, 0, 0, 0, 0, 2} การดำเนินการ 3 − A ={0,0, 0, 0, 0, 0}
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
n :=ขนาดของ A
idx :=-1
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
A[i] :=(A[i] + k - 1) / k
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
ถ้า A[i]>=x แล้ว
x :=A[i]
idx :=ผม
ส่งคืน idx
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def search_index(A, k):
n = len(A)
idx = -1
x = -10**9
for i in range(n):
A[i] = (A[i] + k - 1) // k
for i in range(n):
if (A[i] >= x):
x = A[i]
idx = i
return idx
arr = [4, 3, 6, 8, 3, 10]
K = 4
print(search_index(arr, K))
อินพุต
[4, 3, 6, 8, 3, 10], 4
ผลลัพธ์
5
