每天一道leetcode-33

乔戈里

发布于 2019-09-17 14:18:09

2620

发布于 2019-09-17 14:18:09

文章被收录于专栏：Java那些事

前言

目前准备每天刷一道题leetcode的题目，以此来激励那些零基础入门的人，千万不要被什么科班和非科班的说法吓倒了，计算机这个行业只要你肯努力，没有什么逾越不了的鸿沟。

只要你肯努力，一份努力，一份汗水，在程序员这个职业，你的每一份付出都会得到对应的那一份汇报，尊重学习规律，循序渐进，别想着一口吃个胖子，罗马也不是一天建成的，有朝一日，你终会变成你想成为的人。

题目目前可能需要一定的算法与数据结构基础才能看懂，后序会写一下零基础也能看懂的入门知识，然后就可以看懂我编写的题目了~

案例

题目

leetcode33 在旋转数组中查找一个数n

tag(标签）：二分查找

原题链接：

https://leetcode.com/problems/search-in-rotated-sorted-array/

题目详述

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

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

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

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

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

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

示例 2:

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

题解

先上代码，准备结合着代码进行讲解。

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0)
            return -1;
        int left = 0;
        int right = nums.length - 1;
        while(left <= right)
        {
            int mid = left + (right-left)/2;
            if(nums[mid] == target)
                return mid;
            else if(nums[left] == target)
                return left;
            else if(nums[right] == target)
                return right;
            else{
                if(target > nums[mid])
                {//1
                    if(nums[mid] > nums[0])
                    {//2
                        left = mid + 1;
                    }else
                    {
                        if(target > nums[0])//3
                            right = mid - 1;
                        else
                            left= mid + 1;
                    }
                }
                else{
                    if(nums[mid] > nums[0])
                    {//4
                        if(target < nums[0])//5
                            left = mid + 1;
                        else
                            right = mid - 1;
                    }
                    else{
                        right = mid - 1;
                    }
                }    
            }
        }
        return -1;
    }
}

对于这种题目，数组，有序这两个字眼结合起来，就是要第一时间考虑到二分查找。不懂什么是二分查找的参考我的这篇文章。RNG输了，但我们不能输

假设有这样一个旋转数组[4,5,6,7,8,0,1,2,3],我用图形化的方式表示为下图，方便大家理解，前一段代表4,5,6,7,8，后一段代表0,1,2,3。

下图只是一种情况，后序有多种情况，后序不再是这个数组。

思路：由于无法确定target,nums[mid]谁大谁小，以及target和nums[mid]到底在前半段，还是在后一段，不同的情况下，对于令left = mid+1还是right = mid-1是不一样的情况，所以这里分情况进行讨论，把所有的情况讨论一遍，然后就知道，到底是变化left还是变化right，进而去缩小这个区间，找到我们要找到的数。

target>nums[mid]

情况1

在第18行上，target大于nums[mid]时，紧接着19行，继续讨论nums[mid]与nums[0]的情况，当nums[mid]大于nums[0],也就是说明了nums[mid]一定在前半段，而target是大于nums[mid]的，target必然在前半段，所以这个时候肯定就是要把left=mid+1 才可以去逼近这个target.

情况2

当target大于nums[mid]时候，19行判断后发现nums[mid]小于nums[0],所以这时候，nums[mid]必然在后半段。而targe是大于nums[mid],但target大于nums[mid]的话有两种情况，一种是target在前半段，一种是在后半段，如下两图所示