当前位置: 七九推 > IT编程>开发语言>Java > LeetCode 33. 搜索旋转排序数组

LeetCode 33. 搜索旋转排序数组

2023年01月25日 Java 我要评论
我的leetcode:我的leetcode刷题源码[github]:https://github.com/izhoujie/algorithmciileetcode 33. 搜索旋转排序数组题目假设按

我的leetcode:

我的leetcode刷题源码[github]:https://github.com/izhoujie/algorithmcii

leetcode 33. 搜索旋转排序数组

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 \(\omicron\left(logn\right)\) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

来源:力扣(leetcode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

题目已经要求算法的时间复杂度是\(\omicron\left(logn\right)\),所以肯定还是用二分查找来解决的;

思路1-二分查找

二分查找的前提是数组有序,当前数组是局部有序,所以需要先确定有序的区间再使用二分查找;
大致做法不变,但是在判断大小的时候需要确定有序区间;
步骤:

  1. 左右指针left,right,中间位置mid;
  2. 确定有序区间,当前分为[left,mid]和[mid,right]两个区间,其中之一必是有序递增区间,判断方法就是看target是否在区间中间;
  3. 在有序区间中使用常规的二分查找算法逻辑;

算法复杂度:

  • 时间复杂度: $ {\color{magenta}{\omicron\left(logn\right)}} $
  • 空间复杂度: $ {\color{magenta}{\omicron\left(1\right)}} $

算法源码示例

package leetcode;

/**
 * @author zhoujie
 * @date 2020年1月17日 下午10:22:10 
 * @description: 33. 搜索旋转排序数组
 *
 */
public class leetcode_0033 {
	public static void main(string[] args) {
		int test1[] = { 4, 5, 6, 7, 0, 1, 2 };
		int test2[] = { 1, 3 };
		int test3[] = { 4, 5, 6, 7, 0, 1, 2 };
		system.out.println(new solution_0033().search_1(test1, 0));
		system.out.println(new solution_0033().search_1(test2, 3));
		system.out.println(new solution_0033().search_1(test3, 8));
	}
}

class solution_0033 {
	/**
	 * @author: zhoujie
	 * @date: 2020年2月4日 下午9:39:47 
	 * @param: @param nums
	 * @param: @param target
	 * @param: @return
	 * @return: int
	 * @description: 1-未优化的
	 *
	 */
	public int search_1(int[] nums, int target) {
		if (nums == null) {
			return -1;
		}
		int i = 0, j = nums.length - 1, k;
		while (i <= j) {
			k = (i + j) / 2;
			if (i == j && nums[k] != target) {
				return -1;
			}
			if (nums[k] == target) {
				return k;
			} else if (nums[i] > nums[k] && nums[k] < nums[j]) {
				if (target > nums[k] && target <= nums[j]) {
					i = k + 1;
				} else {
					j = k - 1;
				}
			} else if (nums[i] < nums[k] && nums[k] > nums[j]) {
				if (target >= nums[i] && target < nums[k]) {
					j = k - 1;
				} else {
					i = k + 1;
				}
			} else if (nums[i] <= nums[k] && nums[k] < nums[j]) {
				if (target < nums[k]) {
					j = k - 1;
				} else {
					i = k + 1;
				}
			} else if (target > nums[j]) {
				j = k - 1;
			} else {
				i = k + 1;
			}
		}
		return -1;
	}

	/**
	 * @author zhoujie
	 * @date 2020年1月19日 上午12:13:34 
	 * @description: todo(方法简述) 
	 * @return int 
	 * @updateuser-updatedate:[zhoujie]-[2020年1月19日 上午12:13:34]  
	 * @updateremark:2-思路:关键是找到有序区间,每次的判断仅在有序区间内进行,比较条理清晰;
	 *
	 */
	public int search_2(int[] nums, int target) {
		if (nums == null) {
			return -1;
		}
		int left = 0, right = nums.length - 1;
		int mid;
		while (left <= right) {
			mid = left + (right - left) / 2;
			if (nums[mid] == target) {
				return mid;
				// 若nums[mid] < nums[right],说明右半边有序递增,这里不能先验左半边,因为mid可能与left相等
			} else if (nums[mid] < nums[right]) {
				// 若目标值在右侧有序区间内
				if (target > nums[mid] && target <= nums[right]) {
					left = mid + 1;
					// 目标在左侧区间
				} else {
					right = mid - 1;
				}
				// 若右半边无序,则说明左半边有序,在左半边进行判断
			} else {
				// 若目标值在左半边有序区间内
				if (target >= nums[left] && target < nums[mid]) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			}
		}
		return -1;
	}
}

(0)
打赏 微信扫一扫 微信扫一扫

相关文章:

  • 大专生自学Java到找到工作的经过

    大专生自学Java到找到工作的经过

    刚到大三时前面两年荒废了 什么都没学到所以打算自学个编程 自己对java非常感兴趣 就打算自学java 但是一开始看书 有很多看不懂 非常苦恼 也打算过去培训 ... [阅读全文]
  • 学习Java(重新做人第二天)

    学习Java(重新做人第二天)

    学习Java(重新做人第二天)在mooc上跟翁恺老师学习 ( 面向对象程序设计——Java语言)有秒计时的数字时钟(10分)题目内容:这一周的编程题是需要你在课... [阅读全文]
  • 死磕 java同步系列之JMM(Java Memory Model)

    简介java内存模型是在硬件内存模型上的更高层的抽象,它屏蔽了各种硬件和操作系统访问的差异性,保证了java程序在各种平台下对内存的访问都能达到一致的效果。硬件内存模型在正式讲解j…

    2023年01月24日 开发语言
  • Java单例模式下的MongoDB数据库操作工具类

    Java单例模式下的MongoDB数据库操作工具类

    本文实例讲述了java单例模式下的mongodb数据库操作工具类。分享给大家供大家参考,具体如下:我经常对mongodb进行一些基础操作,将这些常用操作合并到一... [阅读全文]
  • Java中关于内存泄漏出现的原因汇总及如何避免内存泄漏(超详细版)

    android 内存泄漏总结内存管理的目的就是让我们在开发中怎么有效的避免我们的应用出现内存泄漏的问题。内存泄漏大家都不陌生了,简单粗俗的讲,就是该被释放的对象没有释放,一直被某个…

    2023年01月26日 开发语言
  • python女孩入门第一天

    文章目录python的入门介绍python开发环境(IDE)交互模式IDLE开发环境使用入门IDLE介绍IDLE实操IDLE源文件的开发模式IDLE常用快捷键第一个python源程…

    2023年01月26日 开发语言

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。

发表评论

验证码:
Copyright © 2017-2023  七九推 保留所有权利. 粤ICP备17035492号
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com