写点什么

【LeetCode】搜索旋转排序数组 Java 题解

用户头像
HQ数字卡
关注
发布于: 刚刚

题目描述

整数数组 nums 按升序排列,数组中的值 互不相同 。


在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。


给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。


示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0输出:4示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3输出:-1示例 3:
输入:nums = [1], target = 0输出:-1
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法每日一题是查找类题目,这类题目首先可以用朴素算法解决。但朴素算法不是考察的重点。

  • 题目提示整数数组 nums 按升序排列,数组中的值 互不相同并翻转。我们可以使用二分查找的思路进行查找,当 nums[mid] == target 相等时候,就是答案。翻转后的数据是局部有序,比较过程略复杂。实现细节代码如下:

通过代码

  • 朴素算法


class Solution {    public int search(int[] nums, int target) {        int ans = -1;        for (int i = 0; i < nums.length; i++) {            if (nums[i] == target) {                ans = i;                break;            }        }
return ans; }}
复制代码


  • 二分算法


class Solution {    public int search(int[] nums, int target) {        int left = 0, right = nums.length - 1, mid = 0;        while (left <= right) {            mid = left + (right - left) / 2;            if (nums[mid] == target) {                return mid;            }            // 先根据 nums[mid] 与 nums[left] 的关系判断 mid 是在左段还是右段             if (nums[mid] >= nums[left]) {                // 再判断 target 是在 mid 的左边还是右边,从而调整左右边界                 if (target >= nums[left] && target < nums[mid]) {                    right = mid - 1;                } else {                    left = mid + 1;                }            } else {                if (target > nums[mid] && target <= nums[right]) {                    left = mid + 1;                } else {                    right = mid - 1;                }            }        }        return -1;    }}
复制代码

总结

  • 朴素算法的时间复杂度是 O(n),空间复杂度是 O(1)

  • 二分算法的时间复杂度是 O(log n ),空间复杂度是 O(1)

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 2
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】搜索旋转排序数组Java题解