原题链接:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/这道题是二分查找Search
Insert Position的变体,思路在Search
in Rotated Sorted Array中介绍过了,不了解的朋友可以先看看那道题哈。和Search
in Rotated Sorted Array唯一的区别是这道题目中元素会有重复的情况出现。不过正是因为这个条件的出现,出现了比较复杂的case,甚至影响到了算法的时间复杂度。原来我们是依靠中间和边缘元素的大小关系,来判断哪一半是不受rotate影响,仍然有序的。而现在因为重复的出现,如果我们遇到中间和边缘相等的情况,我们就丢失了哪边有序的信息,因为哪边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3},那么旋转之后有可能是{3,3,3,3,3,1,2},或者{3,1,2,3,3,3,3},这样的我们判断左边缘和中心的时候都是3,如果我们要寻找1或者2,我们并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步,直到边缘和中间不在相等或者相遇,这就导致了会有不能切去一半的可能。所以最坏情况(比如全部都是一个元素,或者只有一个元素不同于其他元素,而他就在最后一个)就会出现每次移动一步,总共是n步,算法的时间复杂度变成O(n)。代码如下:
public boolean search(int[] A, int target) {
if(A==null || A.length==0)
return false;
int l = 0;
int r = A.length-1;
while(l<=r)
{
int m = (l+r)/2;
if(A[m]==target)
return true;
if(A[m]>A[l])
{
if(A[m]>target && A[l]<=target)
{
r = m-1;
}
else
{
l = m+1;
}
}
else if(A[m]<A[l])
{
if(A[m]<target && A[r]>=target)
{
l = m+1;
}
else
{
r = m-1;
}
}
else
{
l++;
}
}
return false;
}
以上方法和Search
in Rotated Sorted Array是一样的,只是添加了中间和边缘相等时,边缘移动一步,但正是这一步导致算法的复杂度由O(logn)变成了O(n)。个人觉得在面试中算法复杂度还是很重要的考察点,因为涉及到对算法的理解,大家还是要尽量多考虑哈。
分享到:
相关推荐
find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...
LeetCode-Note-Mary Mary's leetcode notebook The order of problems will follow my summary in the following link: 2020/11/30 stack - easy 2020/12/01 stack - medium 2020/12/02 stack - medium other 2020/...
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 ...
leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running: 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...
leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 add_to_blog_solution_table.py 添加题解地址or题解语言到表格,能同步leetcode新题情况 blog_solution_...
leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array II 3 ...
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
leetcode 1004 leetcode E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E)...
search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
leetcode 2 sum c Leetcode 练习记录 这个专案主要存放我练习Leetcode有针对难度分类的集合题库(Collection Question) 准备方式 分析tag的热门标签,熟悉各个标签解题的思路(解决该标签全部的easy和medium为主),再...
leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two Pointers Array、Two ...
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 暴力枚举...
简单编程: (分析,控制语句)排序 & 查找:二分查找:二分查找进阶:二分查找应用:二分查找应用:二分查找变种:二分查找变种:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/简单数学:...
leetcode添加元素使和等于 leetcode_py Python version of leetcode problems 33 Search in Rotated Sorted Array 问题:找到经过旋转的有序数组中是否有目标的数。 解法:基于二分的方法,根据 target、num[0]、...
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扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
leetcode切割分组 leetcode 加减乘除运算 ...033_search_in_rotated_sorted_array.py # 旋转排序的数列中查找 034_find_first_and_last_position_of_element_in_sorted_array.py # 查找第一次出现和
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 ...
in Rotated Sorted Array II/Solution.java) 2014/10/20 难的 [Java](./src/在旋转排序数组中查找最小值/Solution.java) 2014/10/15 中等的 [Java](./src/最大乘积子阵列/Solution.java) 2014/9/23 中等的 [Java](./...