資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
