频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
Leetcode 33 解题报告
2016-12-29 10:52:00         来源:魔豆(Magicbean)的博客  
收藏   我要投稿

Leetcode 33 解题报告:对于排序之后的数据结构,二分查找是不二法则。本题的关键就在于如何针对旋转之后的排序数组进行二分查找。考虑到数组中没有重复元素(注意这一前提十分关键),可以提供两种思路:

1、两次二分查找:第一次二分查找的目标是找出数组具体在哪个位置做了旋转,这个可以简单地通过比较nums[mid]和它的相邻元素的大小实现。第二次二分查找就简单了:先判断待查找值在左半部分还是右半部分,然后调用普通的二分查找进行查询。

2、一次二分查找:由于数组中没有重复元素,所以思路1中的第一次二分查找其实是不必要的。设中位数为nums[mid],则一次二分查找的思路如下:

1)如果nums[mid] == target,则直接返回mid;

2)如果nums[mid] < nums[right],则说明从mid到right之间是严格递增的。此时可以方便地判断target是否在这一递增区间内:如果是,则在这一递增区间内查找;否则就在另外一个递增区间内找。

3)如果nums[mid] > nums[right],则说明从left到mid之间是严格递增的。此时可以方便地判断target是否在这一递增区间内:如果是,则在这一递增区间内查找;否则就在另外一个递增区间内找。

注意在下面的代码中,即使已经判断出某一区间为严格递增区间了,我们还是用了自己设计的针对旋转排序数组的查找方法。事实上,此时我们可以直接调用标准的二分查找方法,速度应该会更快一些(建议读者自己设计并实现)。

代码:

class Solution {
public:
    int search(vector& nums, int target) {
        if(nums.size() == 0)    return -1;
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
            {
                return mid;
            }
            else if(nums[mid] < nums[right])    // the right part is increasing
            {
                if(nums[mid] < target && target <= nums[right])
                    left = mid + 1;             // might be improved by binarySearch
                else
                    right = mid - 1;
            }
            else                                // the left part is increasing
            {
                if(nums[left] <= target && target < nums[mid])
                    right = mid - 1;            // might be improved by binarySearch
                else
                    left = mid + 1;
            }
        }
        return -1;
    }
};

如果允许数组中有重复元素呢?此时就不能通过判断相互大小每次使搜索空间减半了。具体解法请参考Leetcode 81。

点击复制链接 与好友分享!回本站首页
上一篇:使用BI Publisher开发报表之创建XML数据源
下一篇:使用BI Publisher开发报表之创建一个简单的RTF模板
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站