大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
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:
1if arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y].
0if arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y].
-1if 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: 2
Constraints:
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阿明),一起加油、一起学习进步!
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/160104.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...