网站建设哪个空间比较好,域名批量查询工具,wordpress文章图片保存到本地,网站建设程序员题目描述 题目分析
不含重复元素的题解#xff08;leetcode33#xff09;
这道题也是我们算法课的一道编程题#xff0c;写完以后发现当时的思路和现在没有什么变化#xff0c;果然是自己啊。我的想法是先判断区间整体是升序的还是旋转的#xff0c;如果是升序的就按照正…题目描述 题目分析
不含重复元素的题解leetcode33
这道题也是我们算法课的一道编程题写完以后发现当时的思路和现在没有什么变化果然是自己啊。我的想法是先判断区间整体是升序的还是旋转的如果是升序的就按照正常的二分查找如果是旋转的就判断中轴的落在了左半升区间还是右半升区间问题的关键在于旋转的数组不能简单因为target和中轴的大小判断是在左区间还是右区间因此要分类讨论一下。总之这个思路不是很好因为没有有效利用端点的信息如同官方题解所说我们是可以直接判断出target在哪个区间的。每一次中轴会将数组分成两个部分至少有一个部分是升序的我们能够很简单的判断出target是否在那个升序数组中从而决定在哪个半区间中查找。
我的思路代码
class Solution {
public:int search(vectorint nums, int target) {return bsearch(nums, target, 0, nums.size());}
private:int bsearch(vectorint nums, int target, int l, int r) {if (l r) return -1;int mid (l r) 1;if (nums[mid] target) return mid;if (nums[l] nums[r - 1]) {//升序区间if (nums[mid] target) return bsearch(nums, target, l, mid);else return bsearch(nums, target, mid 1, r);} else {//旋转区间if (nums[mid] nums[l]) {//中心点落在左边升序区间if (nums[mid] target) return bsearch(nums, target, mid 1, r);else {int lr bsearch(nums, target, l, mid);int rr bsearch(nums, target, mid 1, r);if (lr -1) {if (rr -1) return -1; else return rr;} else return lr;}} else {//中心点落在右边升序区间if (nums[mid] target) return bsearch(nums, target, l ,mid);else {int lr bsearch(nums, target, l, mid);int rr bsearch(nums, target, mid 1, r);if (lr -1) {if (rr -1) return -1; else return rr;} else return lr;}}}}
};按照官方题解写的代码
class Solution {
public:int search(vectorint nums, int target) {int l 0, r nums.size(), mid;while (l r) {mid (l r) 1;if (nums[mid] target) return mid;if (nums[mid] nums[l]) {//左半区间是升序if (target nums[l] target nums[mid]) r mid;else l mid 1;} else {//右半区间是升序if (target nums[mid] target nums[r - 1]) l mid 1;else r mid;}}return -1;}
};刚才看了一下题解发现它总是和nums[0]和nums[n-1]比较厉害。
含重复元素的题解
