โปรแกรมค้นหาดัชนีในอาร์เรย์ที่มีองค์ประกอบที่ใหญ่ที่สุดอยู่ใน Python

สมมติว่าเราได้รับคลาสที่เรียกว่า 'TestArray' ที่มีอาร์เรย์ที่ไม่สามารถเข้าถึงได้โดยคลาสอื่น ๆ และฟังก์ชันของสมาชิกสาธารณะสองฟังก์ชัน length() และ comparison() ฟังก์ชัน length() จะคืนค่าความยาวของอาร์เรย์ และฟังก์ชัน Compare() จะคืนค่าที่ต่างกันสามค่าที่เปรียบเทียบอาร์เรย์ย่อยต่างๆ จากอาร์เรย์ ฟังก์ชันรับค่าสี่ค่า l, r, x, y เป็นอินพุตและทำงานในลักษณะนี้ -

• if (array[l] + array[l+1]+......+array[r-1]+array[r])> (array[x] + array[x+1]+... ...+อาร์เรย์[y1]+อาร์เรย์[y]); มันส่งกลับ 1

• if (array[l] + array[l+1]+......+array[r-1]+array[r]) =(array[x] + array[x+1]+... ...+อาร์เรย์[y1]+อาร์เรย์[y]); มันคืนค่า 0

• if (array[l] + array[l+1]+......+array[r-1]+array[r]) <(array[x] + array[x+1]+... ...+อาร์เรย์[y1]+อาร์เรย์[y]); มันคืนค่า -1

เราต้องหาดัชนีขององค์ประกอบสูงสุดในอาร์เรย์โดยไม่ต้องเข้าถึงอาร์เรย์และใช้เฉพาะฟังก์ชันสมาชิกของคลาสเท่านั้น

ดังนั้น หากอินพุตเหมือนกับอาร์เรย์ =[8, 4, 2, 12, 11, 8, 4, 2, 7] ผลลัพธ์จะเป็น 3 องค์ประกอบที่ใหญ่ที่สุดในอาร์เรย์คือ 12 และตั้งอยู่บนดัชนี 3.

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

• n :=length()

• ต่ำ:=0

• สูง :=n - 1

• ในขณะที่ต่ำ <สูง ทำ

  • กลาง :=ค่าพื้นของ (ต่ำ+สูง+1) / 2

  • ถ้า (ต่ำ+สูง+1) mod 2 เหมือนกับ 0 แล้ว

    • res :=เปรียบเทียบ (ต่ำ กลาง -1 กลาง สูง)

    • ถ้า res เท่ากับ 1 แล้ว

      • สูง :=กลาง -1

    • มิฉะนั้น

      • ต่ำ :=กลาง

  • มิฉะนั้น

    • res :=เปรียบเทียบ (ต่ำ กลาง -1 กลาง +1 สูง)

    • ถ้า res เท่ากับ 1 แล้ว

      • สูง :=กลาง -1

    • มิฉะนั้น เมื่อ res เท่ากับ -1 แล้ว

      • ต่ำ :=กลาง -1

    • มิฉะนั้น

      • คืนกลาง

  • ถ้าสูงเท่ากับต่ำแล้ว

    • ผลตอบแทนสูง

• กลับ -1

ตัวอย่าง (Python)

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

class TestArray:
   def __init__(self, array) -> None:
      self.__arr = array

   def length(self):
      return len(self.__arr)

   def compare(self, l, r, x, y):
      val1 = sum(i for i in self.__arr[l:r+1])
      val2 = sum(j for j in self.__arr[x:y+1])
      if val1 > val2:
         return 1
      elif val1 == val2:
         return 0
      elif val1 < val2:
         return -1

def solve(reader):
   n = reader.length()
   low,high = 0,n - 1
   while low < high:
      mid = (low+high+1)//2
      if (low+high+1)%2 == 0:
         res = reader.compare(low,mid-1,mid,high)
         if res == 1:high = mid - 1
         else:low = mid
      else:
         res = reader.compare(low,mid-1,mid+1,high)
         if res == 1:high = mid - 1
         elif res == -1:low = mid + 1
         else: return mid
      if high == low: return high
   return -1

arr_ob = TestArray([8, 4, 2, 12, 11, 8, 4, 2, 7])
print(solve(arr_ob))

อินพุต

[8, 4, 2, 12, 11, 8, 4, 2, 7]

ผลลัพธ์

3