在 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