- 浏览: 173511 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
题目中给定了一个有序数组,但是数组以某个元素作为支点进行了旋转,然后再旋转后的数组中查找目标数字。
这道题我们可以用二分法来解决。二分查找之所以能提高效率就是每次搜索后都可以去掉一半的元素,然后再从剩下的一半元素中查找。这道题的关键点就是每次操作后我们要确定一个有序的序列。当我们得到中间元素m时,如果m元素与target相等,我们就可以直接返回m的下标。如果不相等,我们可以把m元素与左边的第一个元素l相比,如果m元素小于l元素,那么就说明m后面的元素肯定是有序的,我们就从后半部分处理,查看target是否在后半个区域,如果在,我们就让l = m + 1; 如果不在,我们就让l = m - 1。如果m元素大于l元素,则说明m左边的是有序数列,我们就从前半部分处理,如果target在前半部分,让r = m - 1;如果不在,让l = m + 1。代码如下:
(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.
题目中给定了一个有序数组,但是数组以某个元素作为支点进行了旋转,然后再旋转后的数组中查找目标数字。
这道题我们可以用二分法来解决。二分查找之所以能提高效率就是每次搜索后都可以去掉一半的元素,然后再从剩下的一半元素中查找。这道题的关键点就是每次操作后我们要确定一个有序的序列。当我们得到中间元素m时,如果m元素与target相等,我们就可以直接返回m的下标。如果不相等,我们可以把m元素与左边的第一个元素l相比,如果m元素小于l元素,那么就说明m后面的元素肯定是有序的,我们就从后半部分处理,查看target是否在后半个区域,如果在,我们就让l = m + 1; 如果不在,我们就让l = m - 1。如果m元素大于l元素,则说明m左边的是有序数列,我们就从前半部分处理,如果target在前半部分,让r = m - 1;如果不在,让l = m + 1。代码如下:
public class Solution { public int search(int[] nums, int target) { if(nums == null || nums.length == 0) return -1; int l = 0; int r = nums.length - 1; while(l <= r) { int m = l + (r - l) / 2; if(nums[m] == target) return m; if(nums[m] < nums[l]) { if(target > nums[m] && target <= nums[r]) { l = m + 1; } else { r = m - 1; } } else { if(target >= nums[l] && target < nums[m]) { r = m - 1; } else { l = m + 1; } } } return -1; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 226You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 333Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 512Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 430Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 620Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 533Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 861Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 736You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For a undirected graph with tre ...
相关推荐
Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search In Rotated Sorted Array Search In Rotated Sorted Array II 二分搜索/有序矩阵 Kth Smallest Element In A Sorted Matrix Search A 2D ...
Search(二分查找) easy 69: 278: 35: 374: guess number higher or lower 349: intersection of two arrays 350: intersection of two arrays ii medium 33: search in sorted array 81: search in rotated sorted...
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 暴力枚举...
Sorted Array 2 Remove Duplicates from Sorted Array II 3 Search in Rotated Sorted Array 4 Search in Rotated Sorted Array II 5 Median of Two Sorted Arrays 递归实现find kth 6 Longest Consecutive Sequence...
Search in Rotated Sorted Array(搜索旋转排序数组)#数组 2020/12/08 19. Remove Nth Node From End of List(删除链表的倒数第N个节点) 153. Find Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值...
颜色分类leetcode My Leetcode Problems ...Search in Rotated Sorted Array 搜索旋转排序数组 34 Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位
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)
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大小来完成...
leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 ...Rotated Sorted Array Hard -> Medium 35 Search Insert Position Medium -> Easy 36
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. ...
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 ...
Search a 2D Matrix II 替换空格 从尾到头打印链表 重建二叉树 105. Construct Binary Tree from Preorder and Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. ...
leetcode切割分组 leetcode 加减乘除运算 ...033_search_in_rotated_sorted_array.py # 旋转排序的数列中查找 034_find_first_and_last_position_of_element_in_sorted_array.py # 查找第一次出现和
leetcode变形词 :fire: Leetcode / 数据结构和算法 ...in_Rotated_Sorted_Array.java) :pushpin: 数组 :pushpin: 比赛 提交 2020 年 Google Code Jam 资格赛 提交 Google Hash Code 2020 在线资格赛
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/简单数学:...
问题/search-in-rotated-sorted-array.py 中等的 39 问题/组合-sum.py 中等的 40 问题/组合-sum-ii.py 中等的 49 问题/组字谜.py 中等的 50 问题/powx-n.py 中等的 53 问题/最大子数组.py 简单的 55 问题/跳转游戏....
- ADD: In the module FlexUtils added the constant BooleanWords - an array containing the words 'false' and 'true' for saving/reading TBoolProp. - ADD: In the module FlexUtils added the function ...