สมมติว่าเรามีอาร์เรย์ 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