放了个国庆,最近几天效率低下,我忏悔-。-
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
这题剑指offer上有类似的题 :旋转数组的最小值
关键点在于找到一个递增的序列,然后比较序列头尾和target的值。
大家可以想看看,如果A[i]<A[j]则区间[i,j]一定是递增的,画个二维坐标图比较好理解。
算法类似于常规的二分查找:
找到mid。
1. 如果A[start]<=A[mid]说明start到mid一定是一组递增序列:如果A[start]>target,则明显往左走是不可能了,start = mid+1;如果A[start]<=target ,则需要比较递增序列的尾部A[mid]和target的大小,大于target ,则end = mid-1,否则start = mid+1;
2. 如果A[mid]<=A[end]说明mid到end一定是一组递增序列:如果A[end]<target,则明显往右走是不可能了,end = mid-1;如果A[end]>=target,则需要比较比较递增序列的头部A[start]和target的大小,小于target,则start = mid+1; 大于则end = mid-1;
代码:
public static int search(int[] A, int target) { // Note: The Solution object is instantiated only once and is reused by each test case. if(A == null) return -1; int start = 0; int end = A.length-1; while(start<=end){ int mid = start+(end-start)/2; if(A[mid] == target) return mid; if(A[start]<=A[mid]){ if(A[start]>target) start = mid+1; else{ if(A[mid]>target) end = mid-1; else start = mid+1; } } else {//说明A[mid]<=A[end] if(A[end]<target) end = mid-1; else{ if(A[mid]<target) start = mid+1; else end = mid-1; } } } return -1; }
Search in Rotated Sorted Array II
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.
重复的情况下,A[mid]和A[start],A[end]相等的情况需要单独拿出来,当A[mid] 等于A[start]或者A[end]中一个时,根据另一个与A[mid]的大小关系,可以减少一半的范围。但是这三者相等的情况下,则只能顺序判断了。如3 3 3 1 3 和3 1 3 3 3 。
【更新】网上看到的。当这三者相等时,start++,找到不等的地方,继续二分即可。
代码:
public boolean search(int[] A, int target) { // Note: The Solution object is instantiated only once and is reused by each test case. if(A == null ) return false; int start = 0; int end = A.length-1; while(start<=end){ int mid = start+(end-start)/2; if(A[mid] == target) return true; else if(A[start]<A[mid]){//start到mid非降序 if(A[mid]<target) start = mid+1; else { if(A[start]<=target) end = mid-1; else start = mid+1; } }else if(A[start]>A[mid]){//mid到end非降序 if(A[mid]>target) end = mid-1; else{ if(A[end]>=target) start = mid+1; else end = mid-1; } }else{//A[start] = A[mid]!=target if(A[end]!=A[mid]) start = mid+1; else start++; } } return false; }
相关推荐
python python_leetcode题解之081_Search_in_Rotated_Sorted_Array_II
c c语言_leetcode题解之0081_search_in_rotated_sorted_array_ii.zip
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 ...
python python_leetcode题解之153_Find_Minimum_in_Rotated_Sorted_Array.py
python python_leetcode题解之154_Find_Minimum_in_Rotated_Sorted_Array_II.py
leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running: 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...
leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array II 3 ...
- Search in Rotated Sorted Array II(在旋转排序数组中搜索II) - Find Minimum in Rotated Sorted Array(在旋转排序数组中寻找最小值) - Find Minimum in Rotated Sorted Array II(在旋转排序数组中寻找...
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 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 My Leetcode Problems ...Search in Rotated Sorted Array 搜索旋转排序数组 34 Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
leetcode 1004 leetcode E:简单,M:中等,H:...Rotated Sorted Array (M) * -> 부등호 주의, 부등호 하나 틀림 34. Find First and Last Position of Element in Sorted Array (M) 35. Search Insert Position (E)
leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 ...Rotated Sorted Array Hard -> Medium 35 Search Insert Position Medium -> Easy 36
Rotated Sorted Array 问题:找到经过旋转的有序数组中是否有目标的数。 解法:基于二分的方法,根据 target、num[0]、nums[mid] 的大小关系判断向哪个方向搜索。 34 Find First and Last Position of Element in ...
50. Find Minimum in Rotated Sorted Array II – With Duplicates:与上题类似,但是数组中可能存在重复元素。 以上就是该文件中提及的知识点,都是与编程面试密切相关的经典算法和数据结构题目。通过学习和练习...
- Search in Rotated Sorted Array II: 假设按照升序排序的数组在预先未知的某个点上进行了旋转,该问题要求在旋转后的数组中搜索特定元素。 这些知识点涵盖了数据结构和算法的核心概念,以及如何用Python语言实现...
Search in Rotated Sorted Array medium O 54 Spiral Matrix medium O 66 Plus One easy O O 118 Pascal's Triangle easy O O 119 Pascal's Triangle II easy O 要满足只用一个array大小空间O(k) k为input大小来完成...
##### 2.1.3 Search in Rotated Sorted Array **题目描述**:给定一个按非递减顺序排序后旋转得到的数组,找到某个特定目标值的索引位置。若不存在,则返回 `-1`。 **解题思路**: 1. 使用二分查找法,关键在于...