Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
因为rotate的缘故,当我们切取一半的时候可能会出现误区,所以我们要做进一步的判断。具体来说,假设数组是A,每次左边缘为l,右边缘为r,还有中间位置是m。在每次迭代中,分4种情况:
(1)如果target==A[m],那么m就是我们要的结果,直接返回;
(2)如果A[m]<A[r],那么说明从m到r一定是有序的(没有受到rotate的影响),那么我们只需要判断target是不是在m到r之间,如果是则把左边缘移到m+1,否则就target在另一半,即把右边缘移到m-1。
(3)如果A[m]>A[r],那么说明从l到m一定是有序的,同样只需要判断target是否在这个范围内,相应的移动边缘即可。
(4)如果A[m]==A[r], 确定不了,那就r--,往下看一步即可。
算法的平均时间复杂度为O(logn)。最坏情况(比如全部都是一个元素,或者只有一个元素不同于其他元素,而他就在最后一个)就会出现每次移动一步,总共是n步,算法的时间复杂度变成O(n)。
public boolean search(int[] A, int target) { int l=0, r=A.length-1; while(l<=r) { int m = (l+r)>>1; if(A[m] == target) return true; if(A[m]<A[r]) { if(target>A[m] && target<=A[r]) { l = m+1; } else { r = m-1; } } else if(A[m]>A[r]){ if(target>=A[l] && target<A[m]) { r = m-1; } else { l = m+1; } } else { r--; } } return false;
相关推荐
javascript js_leetcode题解之81-search-in-rotated-sorted-array-ii.js
js js_leetcode题解之33-search-in-rotated-sorted-array.js
c语言入门 C语言_leetcode题解之33-search-in-rotated-sorted-array.c
python python_leetcode题解之081_Search_in_Rotated_Sorted_Array_II
c c语言_leetcode题解之0081_search_in_rotated_sorted_array_ii.zip
python python_leetcode题解之154_Find_Minimum_in_Rotated_Sorted_Array_II.py
python python_leetcode题解之153_Find_Minimum_in_Rotated_Sorted_Array.py
- Search in Rotated Sorted Array II: 假设按照升序排序的数组在预先未知的某个点上进行了旋转,该问题要求在旋转后的数组中搜索特定元素。 这些知识点涵盖了数据结构和算法的核心概念,以及如何用Python语言实现...
Search in Rotated Sorted Array(搜索旋转排序数组)#数组 2020/12/08 19. Remove Nth Node From End of List(删除链表的倒数第N个节点) 153. Find Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值...
find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...
- **2.1.4 Search in Rotated Sorted Array II** - 同上,但数组可能包含重复元素。 - **2.1.5 Median of Two Sorted Arrays** - 求两个有序数组的中位数。 - 实现思路:通过比较两个数组的中间值来逐步缩小...
- Search in Rotated Sorted Array II(在旋转排序数组中搜索II) - Find Minimum in Rotated Sorted Array(在旋转排序数组中寻找最小值) - Find Minimum in Rotated Sorted Array II(在旋转排序数组中寻找...
7. **二分查找**:在已排序的数组中查找特定元素或满足条件的元素,如"搜索旋转排序数组"(Search in Rotated Sorted Array)。 8. **位运算**:在数组操作中,位运算有时能提供高效的解决方案,如"无重复字符的...
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
- **在旋转排序数组中搜索 II/Search in Rotated Sorted Array II**: 当数组中存在重复元素时,在被旋转过的排序数组中搜索给定数字。 #### 高级算法技巧 - **数学与位操作(Math and Bit Manipulation)**: 利用数学...
search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
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 lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...
leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running: 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...
简单编程: (分析,控制语句)排序 & 查找:二分查找:二分查找进阶:二分查找应用:二分查找应用:二分查找变种:二分查找变种:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/简单数学:...