Chương trình để tìm ra chỉ mục trong một mảng có phần tử lớn nhất nằm trong Python

Giả sử, chúng ta được cung cấp một lớp gọi là 'TestArray' chứa một mảng mà các lớp khác không thể truy cập và hai hàm thành viên công khai length () và so sánh (). Hàm length () trả về độ dài của mảng và hàm so sánh () trả về ba giá trị khác nhau so sánh các mảng con khác nhau từ mảng. Hàm nhận bốn giá trị l, r, x, y làm đầu vào và hoạt động như thế này -

if (array [l] + array [l + 1] + ...... + array [r-1] + array [r])> (array [x] + array [x + 1] + ... ... + array [y1] + array [y]); nó trả về 1
if (array [l] + array [l + 1] + ...... + array [r-1] + array [r]) =(array [x] + array [x + 1] + ... ... + array [y1] + array [y]); nó trả về 0
if (array [l] + array [l + 1] + ...... + array [r-1] + array [r]) <(array [x] + array [x + 1] + ... ... + array [y1] + array [y]); nó trả về -1

Chúng ta phải tìm ra chỉ số của phần tử lớn nhất trong mảng mà không cần truy cập vào chính mảng đó và chỉ sử dụng các hàm thành viên của lớp.

Vì vậy, nếu đầu vào giống như mảng =[8, 4, 2, 12, 11, 8, 4, 2, 7], thì đầu ra sẽ là 3. Phần tử lớn nhất trong mảng là 12 và nó nằm trên chỉ mục 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=length ()
thấp:=0
cao:=n - 1
trong khi thấp
- mid:=giá trị sàn của (thấp + cao + 1) / 2
- nếu (thấp + cao + 1) mod 2 giống 0, thì
  - res:=so sánh (thấp, giữa 1, giữa, cao)
  - nếu res giống 1 thì
    - cao:=giữa -1
  - nếu không,
    - thấp:=trung bình
- nếu không,
  - res:=so sánh (thấp, giữa 1, giữa + 1, cao)
  - nếu res giống 1 thì
    - cao:=giữa -1
  - ngược lại khi res giống -1 thì
    - thấp:=mid -1
  - nếu không,
    - trở về giữa
- nếu cao bằng với thấp, thì
  - trả lại cao
trả về -1

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Chương trình để tìm ra chỉ mục trong một mảng có phần tử lớn nhất nằm trong Python

Ví dụ (Python)

Đầu vào

Đầu ra