A*******e
发帖数: 2419 | 1 怎么1的难度是hard，2的难度却是medium？
前面270个例子都过了，最后一个例子总是不行。输入是个很长的数组，只有1，查询值
不详，但预期返回真，我的函数返回假。单机上用1查询，返回是真。难道是溢出了？
已经考虑过二分法查找的问题。
代码：
class Solution {
public:
bool search(const vector& nums, int target) {
min_idx_ = FindMinIdx(nums, 0, nums.size() - 1);
len_ = nums.size();
int head = 0, tail = nums.size() - 1;
while (head <= tail) {
int mid = head + (tail - head) / 2;
if (nums[GetIdx(mid)] == target) {
return true;
} else if (nums[GetIdx(mid)] < target) {
head = mid + 1;
} else {
tail = mid - 1;
}
}
return false;
}
private:
int FindMinIdx(const vector& nums, int start, int end) {
assert(start <= end);
if (start == end) {
return start;
} else if (start == end - 1) {
return nums[start] <= nums[end] ? start : end;
}
int mid = (start + end) / 2;
if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
int min_idx_1 = FindMinIdx(nums, start, mid);
int min_idx_2 = FindMinIdx(nums, mid+1, end);
return nums[min_idx_1] <= nums[min_idx_2] ? min_idx_1 : min_idx_
2;
}
if (nums[start] <= nums[mid] && nums[mid] <= nums[end]) {
return start;
}
if (nums[mid] <= nums[end] && nums[end] <= nums[start]){
return FindMinIdx(nums, start, mid);
} else {
return FindMinIdx(nums, mid, end);
}
}
int GetIdx(int n) {
return (n + min_idx_) % len_;
}
int min_idx_;
int len_;
}; |
g**d
发帖数: 383 | 2 返回值是int，如果输入是[1,1....1]，那返回值就是1呗 |
g**d
发帖数: 383 | 3 PS，你的代码太复杂了，本来是一个正常的问题
public int findMin2(int[] nums) {
int start = 0;
int end = nums.length - 1;
while(start < end - 1) {
if(nums[start] < nums[end]) {
return nums[start];
}
int mid = start + (end - start) / 2;
if(nums[mid] > nums[start]) {
start = mid;
} else if(nums[mid] < nums[start]) {
end = mid;
} else {
start ++;
}
}
return Math.min(nums[start], nums[end]);
} |
A*******e
发帖数: 2419 | 4 都是二分法。确实可以简化。不过你这个也不太好懂啊。为何循环条件是start < end
- 1？
【在 g**d 的大作中提到】
: PS，你的代码太复杂了，本来是一个正常的问题
: public int findMin2(int[] nums) {
:
: int start = 0;
: int end = nums.length - 1;
:
: while(start < end - 1) {
: if(nums[start] < nums[end]) {
: return nums[start];
: }
|
i*****h
发帖数: 1534 | 5 这个比较容易理解。
public boolean search(int[] nums, int target) {
int low=0,high=nums.length-1;
while(low
if(nums[low]==target) return true;
++low;
--high;
}
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target) return true;
if((target>nums[mid] && target<=nums[high]) ||
(nums[mid]>nums[high] && (target>nums[mid] ||
target<= nums[high]))){
low=mid+1;
}else{
high=mid-1;
}
}
return false;
} |
A*******e
发帖数: 2419 | 6 我的解法确实有问题，是把findMin直接改成了findMinIdx，然后用它做二分查找的起
点。但问题是min可能有重复，找到的minIdx不能用来标识排序数组的起点。
【在 i*****h 的大作中提到】
: 这个比较容易理解。
: public boolean search(int[] nums, int target) {
: int low=0,high=nums.length-1;
: while(low: if(nums[low]==target) return true;
: ++low;
: --high;
: }
: while(low<=high){
: int mid=(low+high)/2;
|
i*****h
发帖数: 1534 | 7 不用那么复杂。另外我感觉代码太长面试的时候有点吃亏，时间上没优势还有容易有小
bug。
【在 A*******e 的大作中提到】
: 我的解法确实有问题，是把findMin直接改成了findMinIdx，然后用它做二分查找的起
: 点。但问题是min可能有重复，找到的minIdx不能用来标识排序数组的起点。
|
A*******e
发帖数: 2419 | 8 主要是考虑代码复用。
先做了无重复的findMin，推广到findMinIdx，用它解无重复的查找，思路很自然，就
是二分查找加索引偏移修正。
又基于无重复的findMin做了有重复的findMin，想用类似思路推广到findMinIdx再解查
找，结果掉坑里了。有无重复，区别还挺大。
你这个解法思路挺自然，学习了。
【在 i*****h 的大作中提到】
: 不用那么复杂。另外我感觉代码太长面试的时候有点吃亏，时间上没优势还有容易有小
: bug。
|
