`

Leetcode - Search in Rotated Sorted Array II

 
阅读更多
[分析] 同Search in Rotated Sorted Array 的差别在于数组元素可能重复,遇到重复无法推断target所属范围时就一步步移动左边界直到左边界和中间元素不同或者相遇为止。联系Find Minimum in Rotated Sorted Array II进行理解。

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return false;
        int left = 0, right = nums.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return true;
            else if(nums[left] < nums[mid]) {
                if (nums[left] == target) 
                    return true;  
                else if (nums[left] < target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            } else if (nums[left] == nums[mid]) {
                left++;
            } else {
                if (nums[right] == target)
                    return true;
                else if (nums[mid] < target && target < nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return false;
    }
}
分享到:
评论

相关推荐

    扔鸡蛋leetcode-LeetCode-Note-Mary:玛丽的leetcode笔记本

    Search in Rotated Sorted Array(搜索旋转排序数组)#数组 2020/12/08 19. Remove Nth Node From End of List(删除链表的倒数第N个节点) 153. Find Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值...

    lrucacheleetcode-leetcode-in-go:leetcode-in-go

    find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...

    颜色分类leetcode-leetcode-[removed]我对Leetcode问题的解决方案

    颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...

    leetcode296-leetcode-in-py-and-go:Go中的Leetcode

    search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符

    lrucacheleetcode-Coding-Interview:编程面试

    leetcode Coding-Interview A repo for popular coding interview problems mainly from Leetcode. 二分搜索/有序数组旋转 Find Minimum In Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search ...

    leetcodelintcode差异-leetcode-python:leetcode-python

    leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...

    leetcode分类-interview:面试基础算法

    leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running:‍ 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...

    leetcode-7:leetcode 题解,更新中

    简单编程: (分析,控制语句)排序 & 查找:二分查找:二分查找进阶:二分查找应用:二分查找应用:二分查找变种:二分查找变种:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/简单数学:...

    leetcode写题闪退-LeetCode:leetcodeOJ

    leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...

    leetcode2sumc-Leetcode-2020:刷刷Leetcode并作纪录

    leetcode 2 sum c Leetcode 练习记录 这个专案主要存放我练习Leetcode有针对难度分类的集合题库(Collection Question) 准备方式 分析tag的热门标签,熟悉各个标签解题的思路(解决该标签全部的easy和medium为主),再...

    lrucacheleetcode-LeetCode:这个库用于总结leetcode中遇到的习题,期望按照数据结构和常用方法分成2类,进行总结,

    leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array II 3 ...

    leetcode1004-leetcode:leetcode

    leetcode 1004 leetcode E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -&gt; 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E)...

    LeetCode-NoteBook:docsifyjs

    Search in Rotated Sorted Array74. Search a 2D Matrix I240. Search a 2D Matrix II2. Add Two Numbers50. Pow(x, n)34. First & LastPositionElementInSortedArr94. Binary Tree Inorder Traversal144. Binary ...

    leetcode316-leetcode_script:leetcode题解更新脚本

    leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 add_to_blog_solution_table.py 添加题解地址or题解语言到表格,能同步leetcode新题情况 blog_solution_...

    leetcode变形词-Leetcode-Data-Structures-and-Algorithms:该存储库包含基于数据结构和算法的编码问

    leetcode变形词 :fire: Leetcode / 数据结构和算法 ...in_Rotated_Sorted_Array.java) :pushpin: 数组 :pushpin: 比赛 提交 2020 年 Google Code Jam 资格赛 提交 Google Hash Code 2020 在线资格赛

    cpp-算法精粹

    Search in Rotated Sorted Array II Search a 2D Matrix Search a 2D Matrix II Find Minimum in Rotated Sorted Array Find Minimum in Rotated Sorted Array II Median of Two Sorted Arrays H-Index II 暴力枚举...

    Leetcode扑克-coding-interviews:编码面试

    Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...

    LeetCode C++全解

    Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. ...

    leetcode添加元素使和等于-leetcode_py:leetcode的python版本问题

    leetcode添加元素使和等于 leetcode_py Python version of leetcode problems 33 Search in Rotated Sorted Array 问题:找到经过旋转的有序数组中是否有目标的数。 解法:基于二分的方法,根据 target、num[0]、...

    lrucacheleetcode-leetcode:leetcode问题的解决方案

    问题/search-in-rotated-sorted-array.py 中等的 39 问题/组合-sum.py 中等的 40 问题/组合-sum-ii.py 中等的 49 问题/组字谜.py 中等的 50 问题/powx-n.py 中等的 53 问题/最大子数组.py 简单的 55 问题/跳转游戏....

Global site tag (gtag.js) - Google Analytics