放了个国庆,最近几天效率低下,我忏悔-。-
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; }
相关推荐
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 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(搜索旋转排序数组)#数组 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)
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 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 ...
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大小来完成...
Search a 2D Matrix II 替换空格 从尾到头打印链表 重建二叉树 105. Construct Binary Tree from Preorder and Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. ...
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 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two Pointers Array、Two Pointers LeetCode 120. Triangle LintCode 382. Triangle Count/...
find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...
leetcode切割分组 leetcode 加减乘除运算 ...033_search_in_rotated_sorted_array.py # 旋转排序的数列中查找 034_find_first_and_last_position_of_element_in_sorted_array.py # 查找第一次出现和
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](./...
search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
简单编程: (分析,控制语句)排序 & 查找:二分查找:二分查找进阶:二分查找应用:二分查找应用:二分查找变种:二分查找变种:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/简单数学:...