V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  算法

LintCode 领扣 题解丨微软高频题:搜索旋转排序数组

  •  
  •   hakunamatata11 · 2020-08-27 17:40:02 +08:00 · 788 次点击
    这是一个创建于 1309 天前的主题,其中的信息可能已经有所发展或是发生改变。

    假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为 4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1 。你可以假设数组中不存在重复的元素。

    看题解之前,可以试试→在线做题

    例 1:

    输入: [4, 5, 1, 2, 3] and target=1, 
    输出: 2.
    
    

    例 2:

    输入: [4, 5, 1, 2, 3] and target=0, 
    输出: -1.
    
    

    [题解]

    算法:二分

    • 根据题目我们可以知道旋转数组实际上是两个递增数组的组成,且第一个数组中的最小值大于第二个数组的最大值
    • 由于数组中不存在重复的元素,那么我们可以先找到 target 在哪个数组,再进行二分

    代码思路

    • 二分找到第二个数组的起始位置,即整个数组的最小值的位置 minPosition
    • 通过比较 target 和第二个数组最小元素(即最后一个数)大小关系判断 target 在哪一个数组
    • 对 target 所在的数组二分

    复杂度分析

    N 表示为 A 数组的长度

    • 空间复杂度:O(N)
    • 时间复杂度:O(logN)
    public class Solution {
        /**
         * @param A: an integer rotated sorted array
         * @param target: an integer to be searched
         * @return: an integer
         */
        public int search(int[] A, int target) {
            if (A == null || A.length == 0) { 
                return -1; 
            } 
    
            //找到数组最小值位置 minPosition,即第二个数组的起始位置
            int minPosition = 0; 
            intleft = 0; 
            int right = A.length - 1; 
            while (left + 1 < right) { 
                int mid = left + (right - left) / 2; 
                if (A[mid] > A[right]) { 
                   left = mid; 
                } else { 
                    right = mid; 
                } 
            }         
    
            if (A[left] < A[right]) { 
                minPosition = left; 
            } else { 
                minPosition = right; 
            } 
    
            //判断 target 在哪一个数组中
            if (A[A.length - 1] < target) { 
                left = 0; 
                right = minPosition - 1; 
            } else { 
                left = minPosition; 
                right = A.length - 1; 
            }
    
            //对 target 所在数组二分搜索
            while (left + 1 < right) { 
                int mid = left + (right - left) / 2; 
                if (A[mid] < target) { 
                    left = mid; 
                } else { 
                    right = mid; 
                } 
            }          
    
            if (A[left] == target) { 
                return left; 
            } 
            if (A[right] == target) { 
                return right; 
            }         
            return -1; 
        }
    }
    
    

    点此处查看更多题解

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3168 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 12:33 · PVG 20:33 · LAX 05:33 · JFK 08:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.