関小君刷题记

题目大意：

找出大数的下标

给你一个整数数组arr，其中只有一个数字大于其他所有数字，另外的数字都相同。你不能直接访问该数组，只能使用ArrayReader 类的API，它具有以下方法：

1. int compareSub(int l, int r, int x, int y): 其中0 <= l, r, x, y < ArrayReader.length(), l <= r 并且 x <= y. 这个函数用来比较子区间 arr[l..r]内数字和 与子区间 arr[x..y]内数字和的大小关系，返回结果为:
   • 1 当arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y]时.
   • 0 当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]时.
2. int length(): 返回数组长度

你最多只能调用compareSub方法20次，另外上述两个方法的时间复杂度均为O(1)。

请找出数组中最大数的下标。

进阶：

1. 如果数组中有两个数字大于其他数字时你需要如何改进算法？
2. 如果存在一个大于其他的数字以及一个小于其他的数字，你要如何应对？

示例1:

输入: arr = [7,7,7,7,10,7,7,7]
输出: 4
解释: 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.

示例2:

输入: nums = [6,6,12]
输出: 2

提示：

• 2 <= arr.length <= 5 * 10^5
• 1 <= arr[i] <= 100
• 数组中保证除了一个大数外，其他数字都相同。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1533

解题思路分析：

本例类似二分查找。我们将数组从中间一分两半，保证两边的元素个数相同，然后调用compareSub方法，查看哪一部分的和更大，大数肯定在和更大的那半部分中。如果数组长度为奇数时，我们可以将数组分为3部分：[left, mid]，[mid+1, right-1]，right。即除去尾元素后，再将剩下的偶数个元素部分分成等长的两部分。如果这两部分的和相同，那么尾元素即是大数。反之，我们继续在大数所在区域继续使用上述方式寻找。直到区间左右下标相同时，当前下标即是大数所在位置。

实现代码：

public int getIndex(ArrayReader reader) {
    int length=reader.length(); // 查看数组长度
    int l=0,r=length-1; // 定义左右区间
    while(l<r){ // 二分
        int mid=(l+r)/2; // 中间位
        int res; // 两个子区间的比较结果
        int count=r-l+1; // 查看当前区间内元素个数
        if(count%2==0){ // 当前区间元素个数为偶数时
            res=reader.compareSub(l,mid,mid+1,r); // 比较两个区间
        }else{ // 当前区间元素个数为奇数时
            mid--; // 除去尾元素后等分当前区间
            res=reader.compareSub(l,mid,mid+1,r-1); // 比较两个区间
            if(res==0) return r; // 两个区间相同时，大数一定是尾元素r
        }
        if(res==1) r=mid; // 如果前半区间大的话，将区间缩小至前半区间
        else if(res==-1) l=mid+1; // 反之，将区间缩小至后半区间
    }
    return l;
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 100.00% of Java online submissions for Find the Index of the Large Integer.

Memory Usage: 81.4 MB, less than 100.00% of Java online submissions for Find the Index of the Large Integer.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1533-find-the-index-of-the-large-integer-解题思路分析/