- 浏览: 183478 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 265Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 267You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 384Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 374Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 497Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 563Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 475Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 664Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 469The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 429Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 575Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 580Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 426All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 898Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 930Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 602Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 673Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 842Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 783You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 704For 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(在旋转排序数组中搜索II) - Find Minimum in Rotated Sorted Array(在旋转排序数组中寻找最小值) - Find Minimum in Rotated Sorted Array 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...
js js_leetcode题解之33-search-in-rotated-sorted-array.js
python python_leetcode题解之081_Search_in_Rotated_Sorted_Array_II
c语言入门 C语言_leetcode题解之33-search-in-rotated-sorted-array.c
- Search in Rotated Sorted Array II: 假设按照升序排序的数组在预先未知的某个点上进行了旋转,该问题要求在旋转后的数组中搜索特定元素。 这些知识点涵盖了数据结构和算法的核心概念,以及如何用Python语言实现...
javascript js_leetcode题解之81-search-in-rotated-sorted-array-ii.js
c c语言_leetcode题解之0081_search_in_rotated_sorted_array_ii.zip
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 在排序数组中查找元素的第一个和最后一个位
在本资源包中,主题聚焦于C语言的基础学习,特别是针对LeetCode编程挑战中的第33题——"搜索旋转排序数组"(Search in Rotated 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)
- Search in Rotated Sorted Array(旋转排序数组中的搜索):在旋转排序数组中进行查找的问题。 - Search in a Big Sorted Array(在大型排序数组中搜索):在大量数据中进行快速搜索。 除了这些内容之外,Java...
- **2.1.3 Search in Rotated Sorted Array** - 给定一个旋转后的有序数组,找到某个元素的位置。 - 实现思路:利用二分查找法,在处理中间值时考虑数组旋转的情况。 - **2.1.4 Search in Rotated Sorted Array ...
23. **Search in Rotated Sorted Array**:在一个旋转排序数组中查找目标值。根据旋转情况,可能需要对搜索区间进行划分,使用二分查找策略。 以上就是这些题目涉及的算法和数据结构,包括但不限于哈希表、栈、队列...
比如,“搜索旋转排序数组”(Search in Rotated Sorted Array)就是一个典型的应用,数组的一部分是有序的,而另一部分是反向有序的,你需要在这样的数组中找到一个特定的元素。 五、树 树是一种非线性数据结构,...