找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1295|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Search in Rotated Sorted Array II】

[复制链接]

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
发表于 10-12-2014 01:59 AM | 显示全部楼层 |阅读模式

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

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

x
Leetcode通道:https://oj.leetcode.com/problems ... ed-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.

思路:和"Search in Rotated Sorted Array"类似,抓住sorted array这一特性,可以通过一种更加泛型的binary search解决。需要注意的是,当遇到重复元素时,low指针依次递增即可。

代码:

  1. public class Solution {
  2.     public boolean search(int[] A, int target) {
  3.         // Start typing your Java solution below
  4.         // DO NOT write main() function
  5.         int low = 0, high = A.length - 1;
  6.       
  7.         while(low <= high){
  8.             int mid = (low + high) / 2;
  9.             if(A[mid] == target) return true;
  10.             if(A[low] < A[mid]){
  11.                 if(A[low] <= target && target < A[mid])
  12.                     high = mid - 1;
  13.                 else
  14.                     low = mid + 1;
  15.             }else if(A[low] > A[mid]){
  16.                 if(A[mid] < target && target <= A[high])
  17.                     low = mid + 1;
  18.                 else
  19.                     high = mid - 1;
  20.             }<b>else low++; // handle duplications</b>
  21.         }
  22.         return false;
  23.     }
  24. }
复制代码

时间复杂度:O(logn), 空间复杂度:O(1)


本帖被以下淘专辑推荐:

57

主题

4

精华

335

积分

高级会员

Rank: 3Rank: 3

积分
335
发表于 4-12-2015 07:19 PM | 显示全部楼层
这样平均时间复杂度是 O(logn),但似乎最差的情况为 O(n)。
回复 支持 反对

使用道具 举报

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

本版积分规则

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