LeetCode 702. Search in a Sorted Array of Unknown Size
原题链接在这里：https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/
题目：
Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).
You may assume all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.
Example 1:
Input:array= [-1,0,3,5,9,12],target= 9
Output: 4
Explanation: 9 exists innumsand its index is 4
Example 2:
Input:array= [-1,0,3,5,9,12],target= 2
Output: -1
Explanation: 2 does not exist innumsso return -1
Note:
- You may assume that all elements in the array are unique.
- The value of each element in the array will be in the range
[-9999, 9999].
题解：
The range of index could not be over 20000. Because element raget is [-9999, 9999].
Guess the index using binary search, and call the reader.get() on the guess index.
If the return value cur > target, it could be either there is no such index, return is Integer.MAX_VALUE, or it exists, but value is larger. Either way, should continue guessing smaller index.
If cur < target, should continue guessing larger index.
If cur == target, return the guess index.
Time Complexity: O(logn). n = 20000.
Space:O(1).
AC Java:
class Solution {
public int search(ArrayReader reader, int target) {
int l = 0;
int r = 20000;
while(l <= r){
int mid = l + (r-l)/2;
int cur = reader.get(mid);
if(cur > target){
r = mid-1;
}else if(cur < target){
l = mid+1;
}else{
return mid;
}
}
return -1;
}
}
Could use candidate call to get r. while (reader.get(r) < target). r *=2.
Then target index should be (r/2,r].
Time Complexity: O(logn).
Space: O(1).
AC Java:
class Solution {
public int search(ArrayReader reader, int target) {
int r = 1;
while(reader.get(r) < target){
r = r << 1;
}
int l = r >> 1;
while(l <= r){
int mid = l + (r-l)/2;
int cur = reader.get(mid);
if(cur > target){
r = mid-1;
}else if(cur < target){
l = mid+1;
}else{
return mid;
}
}
return -1;
}
}
最新文章
- C# 如何捕获键盘按钮和组合键以及KeyPress/KeyDown事件之间的区别 （附KeyChar/KeyCode值）
- datagridview自动填充列头
- Java汉字排序(3)按笔划排序
- ORA-12545:Connect failed beacuse target host or object does not exist
- (转)CSS行高——line-height
- 新安装 wampserver 出现 You don't have permission to access / on this server. 或者访问数据库出现You don't have permission to access /phpmyadmin/ on this server.（解决方法）转
- CoreAnimation2-视觉效果和变换
- Http请求的 HttpURLConnection 和 HttpClient
- java开发是否一定要使用三层结构
- RMQ 详解
- 解决SQLServer 2008 日志无法收缩，收缩后大小不改变
- JS中遍历语法的比较
- XMPP系列(三）---获取好友列表、添加好友
- [HTML]HTML隐藏文本框的四种方式
- 前端清除缓存方法（微信缓存引起的bug）
- qemu-kvm内存虚拟化2
- ECS——安装nginx
- lldb使用
- MySQL修改版本号教程
- 使用SecureCRT软件运维的配置习惯