数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序找出数组中最大元素所在索引
假设，我们有一个名为“TestArray”的类，它包含一个其他类无法访问的数组，以及两个公共成员函数 length() 和 compare()。函数 length() 返回数组的长度，函数 compare() 返回三个不同的值，比较数组中的各个子数组。该函数接受四个值 l、r、x、y 作为输入，并按如下方式工作：
如果 (array[l] + array[l+1]+......+array[r-1]+array[r]) > (array[x] + array[x+1]+......+array[y1]+array[y])；则返回 1
如果 (array[l] + array[l+1]+......+array[r-1]+array[r]) = (array[x] + array[x+1]+......+array[y1]+array[y])；则返回 0
如果 (array[l] + array[l+1]+......+array[r-1]+array[r]) < (array[x] + array[x+1]+......+array[y1]+array[y])；则返回 -1
我们必须在不访问数组本身，仅使用类的成员函数的情况下找出数组中最大元素的索引。
因此，如果输入类似于 array = [8, 4, 2, 12, 11, 8, 4, 2, 7]，则输出将为 3。数组中最大的元素是 12，它位于索引 3。
为了解决这个问题，我们将遵循以下步骤：
n := length()
low:= 0
high := n - 1
当 low < high 时，执行以下操作：
mid := (low+high+1) / 2 的向下取整值
如果 (low+high+1) mod 2 等于 0，则：
res := compare(low, mid-1, mid, high)
如果 res 等于 1，则：
high := mid -1
否则：
low := mid
否则：
res := compare(low, mid-1, mid+1, high)
如果 res 等于 1，则：
high := mid -1
否则，当 res 等于 -1 时，则：
low := mid -1
否则：
返回 mid
如果 high 等于 low，则：
返回 high
返回 -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
163 次查看
