X

LEETCODE 1533. Find the Index of the Large Integer 解题思路分析

题目大意:

找出大数的下标

给你一个整数数组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]内数字和的大小关系,返回结果为:
    • 1arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y]时.
    • 0arr[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-解题思路分析/
Categories: leetcode
kwantong: