文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

We have an integer array arr, where all the integers in arr are equal except for one integer which is larger than the rest of the integers. You will not be given direct access to the array, instead, you will have an API ArrayReader which have the following functions:

• int compareSub(int l, int r, int x, int y): where 0 <= l, r, x, y < ArrayReader.length(), l <= r and x <= y. The function compares the sum of sub-array arr[l…r] with the sum of the sub-array arr[x…y] and returns:
  1 if arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y].
  0 if arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y].
  -1 if arr[l]+arr[l+1]+...+arr[r] < arr[x]+arr[x+1]+...+arr[y].
• int length(): Returns the size of the array.

You are allowed to call compareSub() 20 times at most. You can assume both functions work in O(1) time.

Return the index of the array arr which has the largest integer.

Follow-up:

• What if there are two numbers in arr that are bigger than all other numbers?
• What if there is one number that is bigger than other numbers and one number that is smaller than other numbers?

Example 1: Input: arr = [7,7,7,7,10,7,7,7] Output: 4 Explanation: The following calls to the API reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]). Thus we know that arr[0] and arr[1] doesn't contain the largest element. reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3]. reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array. Notice that we made only 3 calls, so the answer is valid.Example 2: Input: nums = [6,6,12] Output: 2Constraints: 2 <= arr.length <= 5 * 10^5 1 <= arr[i] <= 100 All elements of arr are equal except for one element which is larger than all other elements.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-index-of-the-large-integer
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

/*** // This is the ArrayReader's API interface.* // You should not implement it, or speculate about its implementation* class ArrayReader {* public:* // 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])* int compareSub(int l, int r, int x, int y);** // Returns the length of the array* int length();* };*/class Solution { public:int getIndex(ArrayReader &reader) {int n = reader.length(), l = 0, r = n-1, midl, midr;int flag;while(l < r){if((r-l)&1)//差為奇數midl = (l+r)/2,midr = (l+r)/2+1;else//偶數midl = midr = (l+r)/2;flag = reader.compareSub(l, midl, midr,r);if(flag > 0)//左邊和大r = midl;else if(flag < 0)//右邊和大l = midr;else//相等找到了return midl;}return l;} };

200 ms 39.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1533. Find the Index of the Large Integer（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。