找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1594|回复: 4
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Search in Rotated Sorted Array】-【刷题第一弹2014】

[复制链接]

21

主题

8

精华

415

积分

高级会员

Rank: 3Rank: 3

积分
415
发表于 10-10-2014 10:42 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 lorenzo 于 10-10-2014 10:48 PM 编辑


leetcode 快速通道:
https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

题目:

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.


回帖方式:

思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)

=========点击传送门查看所有题目哟========
               汇总贴 传送门
=================================

本帖被以下淘专辑推荐:

21

主题

8

精华

415

积分

高级会员

Rank: 3Rank: 3

积分
415
 楼主| 发表于 10-10-2014 10:47 PM | 显示全部楼层
该题是search in rotated sorted array的简单版,不考虑重复情况,则代码非常清晰简单。

section1---mid---section2

思路:如果target 在mid,返回,否则:如果section1是 顺序的,则target 会在哪个section,就递归哪个;再看如果section1不是顺序的,再查找
  1. public class Solution {
  2.     public int search(int[] A, int target) {
  3.         if(A == null) return -1;
  4.         return search(A, 0, A.length, target);
  5.     }
  6.    
  7.     public int search(int[] A, int start, int end, int target){
  8.         if(start - end >= 0) return -1;
  9.         int mid = (start+end)/2;
  10.         if(A[mid] == target) return mid;
  11.         if(A[mid] > A[start]){
  12.             if(target>=A[start] && target<A[mid]) return search(A, start, mid, target);
  13.             else return search(A, mid+1, end, target);
  14.         }
  15.         else{
  16.             if(target>A[mid] && target<=A[end-1]) return search(A, mid+1, end, target);
  17.             else return search(A, start, mid, target);
  18.         }
  19.     }
  20. }
复制代码
回复 支持 反对

使用道具 举报

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 11-15-2014 02:45 AM | 显示全部楼层
  1. class Solution {
  2. public:
  3.     int search(int A[], int n, int target) {
  4.         return search(A, 0, n - 1, target);
  5.     }
  6.    
  7.     int search(int A[], int low, int high, int target) {
  8.         while(low <= high){
  9.             int mid = (low + high)/2;
  10.             
  11.             if(A[mid] == target) return mid;
  12.             if(A[mid] > target){
  13.                 if(A[mid] < A[high]) high = mid - 1;
  14.                 else{
  15.                     int index1 = search(A, low, mid - 1, target);
  16.                     int index2 = search(A, mid + 1, high, target);
  17.                     return index1 == -1 ? index2 : index1;
  18.                 }
  19.             }
  20.             else{
  21.                 if(A[mid] > A[low]) low = mid + 1;
  22.                 else{
  23.                     int index1 = search(A, low, mid - 1, target);
  24.                     int index2 = search(A, mid + 1, high, target);
  25.                     return index1 == -1 ? index2 : index1;
  26.                 }
  27.             }
  28.         }
  29.         return -1;        
  30.     }
  31. };
复制代码

上面的代码没有直接使用二叉查找,将返回值改为bool类型后就可以直接用在Search in Rotated Sorted Array II,而在这个问题中,当然可以在确定子数组为排序数组时,直接调用二叉查找算法,而不是直接递归自身。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表