在 Python 中找出数组中最大元素所在的索引的程序

假设我们有一个名为“TestArray”的类,它包含一个其他类无法访问的数组和两个公共成员函数length()和compare()。该函数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

我们必须在不访问数组本身并且仅使用类的成员函数的情况下找出数组中最大元素的索引。

因此,如果输入类似于 array = [8, 4, 2, 12, 11, 8, 4, 2, 7],那么输出将是 3。数组中最大的元素是 12,它位于索引上3.

示例(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