难度: Medium
Submission
运行时间: 118 ms
内存: 52.9 MB
# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
#class ArrayReader(object):
# # Compares the sum of arr[l..r] with the sum of arr[x..y]
# # return 1 if sum(arr[l..r]) > sum(arr[x..y])
# # return 0 if sum(arr[l..r]) == sum(arr[x..y])
# # return -1 if sum(arr[l..r]) < sum(arr[x..y])
# def compareSub(self, l: int, r: int, x: int, y: int) -> int:
#
# # Returns the length of the array
# def length(self) -> int:
#
class Solution:
def getIndex(self, reader: 'ArrayReader') -> int:
len = reader.length()
left = 0
right = len - 1
half = 0
comp = 0
temp = 0
while len > 0:
len = right - left + 1
half = len // 2
if len % 2 == 0:
comp = 1
else:
comp = 0
temp = reader.compareSub(left, left + half - comp, left + half, right)
if temp == 0:
return left + half - comp
elif temp == 1:
right = left + half - comp
elif temp == -1:
left = left + half
return 0
Explain
本题解通过二分搜索法寻找最大整数的索引。利用题目提供的 `compareSub` API，可以比较两个子数组的和。算法从数组的两端开始，不断将数组一分为二，通过比较两部分的和确定最大元素所在的部分，并在该部分继续搜索。如果两部分和相等，则直接返回中间的索引。否则，根据比较结果调整搜索范围，继续在较大的一边进行搜索。这种方法逐步缩小搜索范围，直到找到最大元素的位置。
时间复杂度: O(log n)
空间复杂度: O(1)
# 解决方案类
class Solution:
def getIndex(self, reader: 'ArrayReader') -> int:
len = reader.length() # 获取数组长度
left = 0 # 左索引初始化
right = len - 1 # 右索引初始化
half = 0 # 初始化中点偏移量
comp = 0 # 比较结果初始化
temp = 0 # 临时变量用于存储比较结果
while len > 0:
len = right - left + 1 # 更新当前搜索范围的长度
half = len // 2 # 计算中点位置
if len % 2 == 0:
comp = 1 # 如果长度为偶数，调整半段长度以平衡两边的元素数量
else:
comp = 0 # 如果长度为奇数，不需要调整
temp = reader.compareSub(left, left + half - comp, left + half, right) # 比较两个子数组的和
if temp == 0:
return left + half - comp # 如果两个子数组的和相等，则返回中点索引
elif temp == 1:
right = left + half - comp # 如果左边数组的和较大，则在左侧部分继续搜索
elif temp == -1:
left = left + half # 如果右边数组的和较大，则在右侧部分继续搜索
return 0 # 如果上述循环无法找到最大元素，返回0（正常情况不会发生）
Explore
在二分搜索法中，确保`compareSub` API正确处理数组边界和中点计算，主要依赖于准确地定义和更新左右索引`left`和`right`以及正确计算中点偏移量`half`。`left`和`right`在每次迭代中被更新，以指向当前考虑的子数组的边界。中点`half`是根据当前子数组的长度动态计算的，确保每次比较的两个子数组均分整个考虑的范围。特别是在偶数长度的数组中，通过适当的调整（使用`comp`变量），可以确保两个子数组包含相等数量的元素，从而避免任何一个子数组不被完全比较的情况。
当`compareSub`返回0，即两个子数组的和相等时，选择返回`left + half - comp`作为索引是因为在当前的实现中，这一位置代表了中点或中点附近的元素。此时假设最大值可能出现在中点附近，因此返回此索引。然而，这并不意味着最大元素总是位于中间，而是在这种特定的实现和假设下，选择中点作为最可能的候选。实际情况中，最大元素可能位于数组的任何位置，这只是一种简化操作，实际应用中可能需要更精确的逻辑来确定最大值的确切位置。
`temp`变量存储的是`compareSub`函数的返回值，它表示两个子数组和的比较结果。如果`temp`为1，则表示左侧子数组的和大于右侧子数组的和，因此搜索范围更新为左侧子数组；如果`temp`为-1，则表示右侧子数组的和大于左侧子数组的和，因此搜索范围更新为右侧子数组。这样，`temp`变量直接决定了搜索的方向，帮助算法在可能包含最大元素的子数组中继续进行搜索。
在二分搜索中，`comp`变量用于处理数组长度为偶数时的情况。偶数长度意味着无法直接平均分为两个完全相等的子数组，因此通过调整`comp`的值（设为1），确保两个子数组中一个包含中点而另一个不包含，从而使两个子数组的元素数量尽可能接近。这种处理方式背后的逻辑是为了尽可能保持两个比较子数组的平衡，避免因为元素数量的差异导致比较结果的偏差。