精华内容
下载资源
问答
  • 剑指 Offer 11. 旋转数组的最小数字 153. 寻找旋转排序数组中的最小值 154. 寻找旋转排序数组中的最小值 II 33. 搜索旋转排序数组

    153. 寻找旋转排序数组中的最小值

    题目

    153. 寻找旋转排序数组中的最小值

    假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

    请找出其中最小的元素。

    示例 1:
    输入:nums = [3,4,5,1,2]
    输出:1

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

    示例 3:
    输入:nums = [1]
    输出:1

    解法

    二分查找

    使用二分搜索,在二分搜索中需要找到区间的中间点并根据某些条件决定去区间左侧还是右侧。
    本题中数组被旋转了,所以简单的二分查找不可用。
    使用改进的二分查找。判断条件与标准的二分搜索不同。
    如果数组没有被旋转,是升序排列,满足last element > first element。
    旋转之后可以找到一个变化点,其左边的序列是递增的,右边的序列也是递增的。但是该变化点左边的值要大于右边的值。
    变化点的特点如下:
    1。所有变化点左侧元素>数组第一个元素
    2. 所有变化点右侧元素<数组第一个元素

    算法如下:

    1. 找到数组的中间元素mid
    2. 如果mid>数组第一个元素,需要在mid右边搜索变化点
    3. 如果mid<数组第一个元素,需要在mid左边搜索变化点
    4. 找到变化点时停止搜索,以下条件满足一个时:
      nums[mid] > nums[mid + 1] 因此mid+1是最小值
      nums[mid - 1] > nums[mid] 因此mid是最小值
     public int findMin(int[] nums) {
            if (nums.length == 1) {
                return nums[0];
            }
            int left = 0;
            int right = nums.length - 1;
            // 如果该函数是升序排序的,没有旋转
            if (nums[right] > nums[0]) {
                return nums[0];
            }
            while (left <= right) {
                int mid = left + (right - left) / 2;
                // 变化点的两个条件
                if (nums[mid] > nums[mid + 1]) {
                    return nums[mid + 1];
                }
                if (nums[mid - 1] > nums[mid]) {
                    return nums[mid];
                }
                if (nums[mid] > nums[0]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return -1;
        }
    

    剑指 Offer 11. 旋转数组的最小数字

    题目

    剑指 Offer 11. 旋转数组的最小数字

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。

    示例 1:

    输入:[3,4,5,1,2]
    输出:1
    示例 2:

    输入:[2,2,2,0,1]
    输出:0

    解法

    在这里插入图片描述

    考虑数组的最后一个元素x:
    在最小值右侧的元素,它们的值一定都小于x
    左侧的元素,它们的值一定都大于x
    根据这个性质,通过二分查找的方法找出最小值。
    在二分查找的每一步中,左边界为low,右边界为high,区间的中点为middle。
    将中间元素numbers[mid]与右边界元素numbers[high]进行对比。可能存在以下三种情况:
    第一种情况是numbers[mid] < numbers[high]。说明numbers[mid]是最小值右侧的元素,因此可以忽略二分查找的右半部分
    在这里插入图片描述
    第二种情况是numbers[mid] > numbers[high]。说明numbers[mid]是最小值右侧的元素,因此可以忽略二分查找的左半部分
    在这里插入图片描述
    第三种情况是numbers[mid] == numbers[high]。由于重复元素的存在,并不能确定numbers[mid]在最小值的左侧还是右侧。
    在这里插入图片描述
    只知道的是由于值相同,无论numbers[high]是不是最小值,都有一个替代品numbers[mid],因此忽略二分查找区间的右端点。

        public int minArray(int[] numbers) {
            int left = 0;
            int right = numbers.length - 1;
            while (left < right) {
                int middle = left + (right - left) / 2;
                if (numbers[middle] < numbers[right]) {
                    right = middle;
                } else if (numbers[middle] > numbers[right]) {
                    left = middle + 1;
                } else {
                    right--;
                }
            }
            return numbers[left];
        }
    

    154. 寻找旋转排序数组中的最小值 II

    本题与剑指offer 11为同一个题。

    33. 搜索旋转排序数组

    题目

    33. 搜索旋转排序数组

    整数数组 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

    解法

    使用二分查找。
    在常规二分查找的时候查看当前mid为分割位置分割出来的两个部分
    [left, mid] 和 [mid + 1, right]两个部分。
    哪个部分是有序的,并根据有序的那个部分确定我们该如何改变二分查找的上下界,
    如果[left, mid - 1]是有序数组,且target的大小满足[nums[left], nums[mid]],则将搜索范围切换到[left, mid - 1]。否则在[mid + 1,right]中寻找
    如果[mid, right]是有序数组,且target的大小满足[nums[mid+1], nums[right]],则将搜索范围切换到[mid + 1, right]。否则在[left, mid - 1]中寻找

     public int search(int[] nums, int target) {
            int n = nums.length;
            if (n == 0) {
                return -1;
            }
            if (n == 1) {
                return nums[0] == target ? 0 : -1;
            }
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
                    return mid;
                }
                // 如果左边的部分有序
                if (nums[0] <= nums[mid]) {
                    // 如果目标值落在左边的范围内,则在左边查找。否则在右边查找
                    if (nums[0] <= target && target < nums[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                    // 如果右边的部分有序
                } else {
                    // 如果目标值落在右边的范围内,则在右边查找。否则在左边查找
                    if (nums[mid] < target && target <= nums[n - 1]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
            return -1;
        }
    

    81. 搜索旋转排序数组 II

    展开全文
  • 开篇闲话,由于忙于准备找工作,其实我是有每天刷算法题的,但感觉写博客很耗时间,所以一直没有在博客中记录。春招找的让我差点得抑郁症了,贼难受。...旋转排序数组问题—153. 寻找旋转排序数组中的最小值&am...

    开篇闲话,由于忙于准备找工作,其实我是有每天刷算法题的,但感觉写博客很耗时间,所以一直没有在博客中记录。春招找的让我差点得抑郁症了,贼难受。投了40多家公司了,但目前只有六七家提供了笔试机会,学历以及自己简历的项目经历没有优势,另外互联网寒冬更是雪上加霜。。。
    许愿:希望春招能拿个让自己满意的offer!!!哈哈哈,开始迷信一把了!!!

    旋转排序数组问题—153. 寻找旋转排序数组中的最小值&&33. 搜索旋转排序数组&&81. 搜索旋转排序数组 II

    一、153. 寻找旋转排序数组中的最小值

    1. 题目
    题目链接

    2. 题目分析
    旋转数组,实际上就是左右整体互换,也就导致出现了两个递增序列。
    无重复数组
    3. 解题思路
    如果直接遍历查找,时间复杂度是O(n),不符合要求,题目要求O(logn)。部分有序+O(logn)的条件,暗示这个查找可以使用二分查找。
    如果这个升序排序的有序数组确实按照某个未知的位置旋转,只有两种可能:

       1.a [mid]  > a [left] || a [mid]> a [right],所以,mid位于较大的那部分,较小的部分位于mid右边,应该向右走;
    
       2.a [mid] <a [left] || a [mid] <a [right],所以,mid位于较小的那部分,为了找到最小的元素,应该向左走;
    
       如果这个数组没有旋转(或者是循环旋转完),只需要往左走,a[mid]总是< a[right];
    
       结论:mid > right,向右走;mid < right,向左走;
    

    4. 代码实现(java)

    class Solution {
        public int findMin(int[] nums) {
            if (nums == null){
                return -1;
            }
            if (nums.length == 1){
                return nums[0];
            }
            int mid=0;
            int high = nums.length-1;
            int low = 0;
            while (low <= high){
                mid = low + (high-low)/2;
                if (mid > 0 && nums[mid] <= nums[mid-1]){
                    return nums[mid];
                }
                if (nums[mid] < nums[low] || nums[mid] < nums[high]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }
            return nums[0];
        }
    }
    

    二、33. 搜索旋转排序数组

    1. 题目
    题目链接

    2. 题目分析
    无重复元素。

    3. 解题思路
    上一道寻找旋转排序数组中最小值的问题,我们当时使用num[left]和num[mid]的大小关系来判断此时mid指向的元素是在数组的前半段还是后半段。这道题和上一道稍微有点不一样。因此,我们可以先判断经过二分之后的两段数组哪个是排好序的,再判断target是否在这段排好序的数组当中,是的话,就简单了,简单二分搜索即可,不在的话,继续分析上回没排好序的数组,递归的按照以上的逻辑继续查找即可。
    当我们二分查找时,有两种可能,一种是选择的部分一个递增序列,而另一种可能选择的部分横跨两个递增序列。
    我们只要每次处理递增序列那部分就好。

    可以分以下三种情况讨论:

    1. num[mid] = target,那么找到了,不用继续找了

    2. num[mid] >= num[left] 那么此时mid左端,一直到left的数组是排好序的。可以继续细分为两种情况:
      (1)num[mid] > target && target >= num[left],说明此时target在mid左侧排好序的数组内。用二分查找处理这段数组即可
      (2)如果不符合(1)中的条件,处理mid右侧的数组(还是按照先寻找排序数组,再二分查找的逻辑)

    3. 第2点中的条件不成立,那么此时mid右端,一直到right的数组是排好序的。可以继续细分为两种情况:
      (1)num[mid] < target && target <= num[right],说明此时target在mid右侧排好序的数组内。用二分查找处理这段数组即可
      (2)如果不符合(1)中的条件,处理mid左侧的数组(还是按照先寻找排序数组,再二分查找的逻辑)

    4. 代码实现(java)

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

    三、81. 搜索旋转排序数组 II

    1. 题目
    题目链接

    2. 题目分析
    有重复元素。

    3. 解题思路
    这道题与之前Search in Rotated Sorted Array类似,问题只在于存在重复元素。那么和之前那道题的解法区别就是,不能通过比较A[mid]和边缘值来确定哪边是有序的,会出现A[mid]与边缘值相等的状态。当中间值与边缘值相等时,让指向边缘值的指针分别往前移动,忽略掉这个相同点,再用之前的方法判断即可。
    而如果解决掉重复之后,利用一个性质,旋转后两部分一定有一部分有序,那么通过判断左边还是右边有序分为两种情况。然后再判断向左走还是向右走。
    这一改变增加了时间复杂度,试想一个数组有同一数字组成{1,1,1,1,1},target=2, 那么这个算法就会将整个数组遍历,时间复杂度由O(logn)升到O(n)。

    4. 代码实现(java)

    class Solution {
        /**
        不能通过比较A[mid]和边缘值来确定哪边是有序的,会出现A[mid]与边缘值相等的状态。当中间值与边缘值相等时,让指向边缘值的指针分别往前移动,忽略掉这个相同点,再用之前的方法判断即可。
    而如果解决掉重复之后,利用一个性质,旋转后两部分一定有一部分有序,那么通过判断左边还是右边有序分为两种情况。然后再判断向左走还是向右走。
        */
        public boolean search(int[] nums, int target) {
            if(nums == null || nums.length == 0){
                return false;
            }
            int left =0;
            int right = nums.length-1;
            int mid;
            while(left <= right){
                mid= (right + left)>>1;
                if(nums[mid] == target){
                    return true;
                }
                if(nums[mid] == nums[left]){
                    left++;
                }else if(nums[mid] > nums[left]){
                    if(nums[mid] > target && target >= nums[left]){
                        right = mid-1;
                    }else{
                        left = mid+1;
                    }
                }else{
                    if(nums[mid] < target && target <= nums[right]){
                        left = mid+1;
                    }else{
                        right = mid-1;
                    }
                }
            }
            return false;
        }
    }
    
    展开全文
  • 搜索旋转排序数组题目描述解答81. 搜索旋转排序数组 II题目描述解答 33. 搜索旋转排序数组 题目描述 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1...

    33. 搜索旋转排序数组

    题目描述

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

    ( 例如,数组 [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

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解答

    由于要求时间复杂度是 O(log n) ,所以采用直接二分法,中心点的左右两侧必有至少一侧是有序的

    class Solution:
        def search(self, nums, target):
            if len(nums) == 0:
                return -1
            l = 0
            r = len(nums) - 1
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] < nums[r]:  # mid落在了右边的有序数组中
                    if nums[mid] < target <= nums[r]:  # 如果target在区间(nums[mid],nums[r]] 内 
                        l = mid + 1
                    else:
                        r = mid - 1
                else:  # mid落在了左边的有序数组中
                    if nums[l] <= target < nums[mid]:  # # 如果target在区间[nums[l],nums[mid]) 内 
                        r = mid - 1
                    else:
                        l = mid + 1
            return -1
    

    81. 搜索旋转排序数组 II

    题目描述

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

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

    编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。

    示例 1:

    输入: nums = [2,5,6,0,0,1,2], target = 0
    输出: true
    示例 2:

    输入: nums = [2,5,6,0,0,1,2], target = 3
    输出: false
    进阶:

    这是 搜索旋转排序数组 的延伸题目,本题中的 nums 可能包含重复元素

    解答

    二分法,判断二分点,几种可能性

    直接nums[mid] == target

    当数组为[1,2,1,1,1],nums[mid] == nums[left] == nums[right],需要left++, right --;

    nums[left]<= nums[mid],说明是在左半边的递增区域

    ​ a. nums[left] <=target < nums[mid],说明targetleftmid之间.我们令right = mid - 1;

    ​ b. 不在之间, 我们令 left = mid + 1;

    nums[mid] < nums[right],说明是在右半边的递增区域

    ​ a. nums[mid] < target <= nums[right],说明targetmidright之间,我们令left = mid + 1

    ​ b. 不在之间,我们令right = mid - 1;

    时间复杂度:O(logn)

    class Solution:
        def search(self, nums, target):
            if not nums:
                return False
            n = len(nums)
            l, r = 0, n - 1
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] == target:
                    return True
                if nums[mid] == nums[l] == nums[r]:
                    l += 1
                    r -= 1
                elif nums[mid] <= nums[r]:
                    if nums[mid] < target <= nums[r]:
                        l = mid + 1
                    else:
                        r = mid - 1
                else:
                    if nums[l] <= target < nums[mid]:
                        r = mid - 1
                    else:
                        l = mid + 1
            return False    
    

    注意:
    第二题与第一题在代码上的区别在于:
    1.第二题加入了对重复元素的判断,当三者重复时,左指针向右移,右指针向左移

    	if nums[mid] == nums[l] == nums[r]:
    		l += 1
            r -= 1
    

    2.在判断nums[mid]值的时候,对判断符号做了改变

    第一题是

    	elif nums[mid] < nums[r]
    

    第二题是

    	elif nums[mid] <= nums[r]
    

    参考:
    33. 搜索旋转排序数组
    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-by-lukelee
    81. 搜索旋转排序数组 II
    https://leetcode-cn.com/problems/two-sum/solution/er-fen-by-powcai/

    展开全文
  • 33. 搜索旋转排序数组 Leetcode 解答 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,如果数组中存在这个目标值,则...

    33. 搜索旋转排序数组

    33. 搜索旋转排序数组 解答

    类似:81. 搜索旋转排序数组 II 解答

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

    ( 例如,数组 [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

    两边总有一遍是有序的;每次判断一下有序的那边有没有target,有的话就从里面找;没有就从另一半找
    
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left=0,right=nums.size()-1;
            int mid=left + (right-left)/2;
            while(left<=right){
                mid=left + (right-left)/2;
                if(nums[mid]==target) return mid;
                if(nums[left]==nums[mid]){  //81题
                    left++;
                    continue;
                }
                if(nums[left] <= nums[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;
        }
    };
    
    展开全文
  • 搜索旋转排序数组

    2020-04-27 16:12:39
    搜索旋转排序数组 4.27搜索旋转排序数组 照升序排序的数组在预先未知的某个点上进行了旋转。 由这句话可知,后半部分一定比前半部分都小。 我们设前半部分为第一部分,后半部分为第二部分。 如果target小于数组最后...
  • 33.搜索旋转排序数组 解题思路: 因为有序数组nums在随机循环后,其实可以看作是由一个升序数组和一个降序数组组成的数组,所以可以对两部分分别进行二分查找。 如果数组的长度为0,直接返回-1; 如果数组的长度为...
  • 搜索旋转排序数组 思路 代码 class Solution: ### 1228 二分法(40 ms,15.2 MB) def search(self, nums: List[int], target: int) -> int: # 若为空数组,直接返回-1 if not nums: return -1 # 初始化...
  • 搜索旋转排序数组 题意:假设按照升序排序的数组在预先未知的某个点上进行了旋转。 例如,数组 [0,1,2,,4,5,6,7] 旋转为 [4,5,6,7,0,1,2],搜索一个给定的target,如果数组中存在这个目标值,则返回它的索引,否则...
  • 假设有一个排序的按未知的旋转旋转数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。 你可以假设数组中不存在重复的元素...
  • 在看剑指offer时遇到了这个题目:寻找旋转排序数组中的最小值 II 假设按照升序排序的数组在预先未知的某个点上进行了...看到这个题目第一时间就想起了LeetCode81:搜索旋转排序数组 II。 首先先看看这两个题目的共...
  • 旋转排序数组其实是由两个递增子数组组成,且前一个子数组中的任意元素都大于后一个数组中元素。left,right分别是指向数组首尾的两个指针。循环条件:left&lt;=right若A[mid]==target,表示若A[mid]&gt;A...
  • class Solution { public: int findMin(vector<int>& nums) { int left = 0; int right = nums.size() - 1; /* 左闭右闭区间,如果用右开区间则不方便判断右值 */ ...
  • LeetCode题解:搜索旋转排序数组

    千次阅读 多人点赞 2020-12-11 09:42:37
    搜索旋转排序数组(middle) 更好的阅读体验应该是: 审题-思考 答题 整理-归纳 一、题目 LeetCode:33.搜索旋转排序数组 给你一个整数数组 nums ,和一个整数 target 。 该整数数组原本是按升序排列,但输入时...
  • 搜索旋转排序数组 II

    2020-04-27 11:32:10
    81. 搜索旋转排序数组 II 来源: LeetCode 81. 搜索旋转排序数组 II 题目描述 81. 搜索旋转排序数组 II 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,609
精华内容 14,643
关键字:

搜索旋转排序数组