LEETCODE 33. 搜索旋转排序数组

LEETCODE 33. 搜索旋转排序数组

Comments 0 Comment

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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

解法一

数组[0,1,2,4,5,6,7]，经过了旋转，可能会变成下面这样:

上图中除了第四个数组没变动，其他三个数组都有这么一个特点:

存在某个下标i，使得num[i]大于nums[i+1]。

因为输入的是升序的，正常来说nums[i+1]应当是大于num[i]，现在反而是小于，说明找到了旋转点。num[i+1]就是数组中最小值。

找到数组中的最小值有什么用呢？我们看下面这个数组

蓝色部分的4,5,6,7是升序的，绿色部分的0,1,2,3也是升序的。最小值0将整个数组分成两段，而这两段都是升序的。
如果蓝色部分最小值<=target<=蓝色部分最大值，那么结果肯定是在蓝色部分，又因为这部分是升序的，所以用正常的二分查找就可以找target了。
同理，如果绿色部分最小值<=target<=绿色部分最大值，那就用二分查找在绿色部分进行查找。

现在问题就转换为如何找到数组中的最小值了，如果找到了最小值，接着再用正常的二分查找就可以搞定了。
下面我们来看看如何查找最小值。
我们仍然用二分查找的思路，假设中间点nums[mid]>=num[0]，那么可以推断出[nums[0],nums[mid]] 这段是升序的，它不满足我们之前说的旋转点条件nums[i]>nums[i+1]，说明最小值肯定是在mid下标的右侧。

如果是下面这种情况，nums[mid]<nums[0]，说明[nums[0]，nums[mid]]这段不是有序的，那么我们要找的最小值就包含在[nums[0]，nums[mid]]之间。

按照上述分析，查找最小值的过程如下:

  1. nums[0]<=nums[max]说明整个数组是有序的，下标0就是最小值
  2. 如果num[i]>nums[i+1]，不满足升序，说明mid+1就是最小值，退出查找
  3. 如果中间值numd[mid]>=nums[0]说明数组左边是有序的，最小值应该在右边
  4. 如果中间值nums[mid]<nums[0]说明数组左边是无序的，最小值应该在数组左边

动画演示:

java代码:

class Solution {
	public int search(int[] nums, int target) {
		if(nums==null || nums.length==0) {
			return -1;
		}
		//查找最小值的下标
		int minIndex = findMin(nums);
		//如果最小值下标为0，说明整个数组是有序的
		if(minIndex==0) {
			return binarySearch(nums,0,nums.length-1,target);
		}
		//最终结果在[0,min_index-1]中
		if(nums[0]<=target) {
			return binarySearch(nums,0,minIndex,target);
		}
		//最终结果在[min_index-1,length-1]中
		return binarySearch(nums,minIndex,nums.length-1,target);
	}
	
	//正常的二分查找
	private int binarySearch(int[] nums,int begin,int end,int target) {
		while(begin<=end) {
			int mid = begin+(end-begin)/2;
			if(nums[mid]>target) {
				end = mid-1;
			}
			else if(nums[mid]<target) {
				begin = mid+1;
			}
			else {
				return mid;
			}
		}
		return -1;
	}
	
	//查找最小值的下标
	private int findMin(int[] nums) {
		int begin = 0;
		int end = nums.length-1;
		//如果第一个值比最后一个值小，说明整个数组是有序的
		if(nums[begin]<=nums[end]) {
			return begin;
		}
		while(begin<=end) {
			int mid = begin+(end-begin)/2;
			//前一个值比后一个值大，找到了旋转点
			if(mid<nums.length-1 && nums[mid]>nums[mid+1]) {
				return mid+1;
			}
			//中间点大于等于第一个元素，左半边是有序的，转去右边查找
			if(nums[mid]>=nums[0]) {
				begin = mid+1;
			//左边是无序的，继续在左边查找	
			} else {
				end = mid-1;
			}
		}
		return 0;
	}
}

python代码:

class Solution(object):
	def search(self, nums, target):
		if not nums:
			return -1
		n = len(nums)
		# 查找最小值的下标
		def findMin():
			begin = 0
			end = n-1
			# 如果第一个值比最后一个值小，说明整个数组是有序的
			if nums[begin]<=nums[end]:
				return begin
			while begin<=end:
				mid = begin+(end-begin)//2
				# 前一个值比后一个值大，找到了旋转点
				if mid<n-1 and nums[mid]>nums[mid+1]:
					return mid+1
				# 中间点大于等于第一个元素，左半边是有序的，转去右边查找	
				if nums[0]<=nums[mid]:
					begin = mid+1
				# 左边是无序的，继续在左边查找		
				else:
					end = mid-1
			return 0
		# 正常的二分查找	
		def binarySearch(begin,end):
			while begin<=end:
				mid = begin+(end-begin)//2
				if nums[mid]>target:
					end = mid-1
				elif nums[mid]<target:
					begin = mid+1
				else:
					return mid
			return -1
		# 查找最小值的下标	
		minIndex = findMin()
		# 如果最小值下标为0，说明整个数组是有序的
		if minIndex==0:
			return binarySearch(0,n-1)
		# 最终结果在[0,min_index-1]中	
		if nums[0]<=target:
			return binarySearch(0,minIndex-1)
		# 最终结果在[min_index-1,length-1]中	
		return binarySearch(minIndex,n-1)

解法二

假设以mid为中间点，可以看到无论mid落在哪里，肯定有一边是有序的。因为某一边肯定是有序的，我们利用有序这个条件，就可以判断出target落在哪一边。

假设我们已经确定了mid的下标位置，目标值target所在的位置可能有如下几种情况。
第一种(见下图)很简单，mid指向的值正好就等于target，直接返回即可

第二种情况(见下图)，如果mid左侧是有序的，那么target要么落在mid的左侧，要么落在mid的右侧。
如果是落在左侧，那么一定满足arr[begin]<=target<=arr[mid]，继续往左边搜索。
如果是落在无序的右侧，那么一定不满足arr[begin]<=target<=arr[mid]这个条件，继续往右侧搜索。

第三种情况(见下图)，mid的左侧是无序的，那么右侧肯定是有序的。
如果target落在右侧，那么一定满足nums[mid]<target<=nums[end]，继续往右搜索。
如果落在无序的左侧，那么那么一定不满足nums[mid]<target<=nums[end]  继续往左搜索。

按照上述分析，可以总结出查找过程如下:

  1. 如果nums[mid]==target，找到目标值直接返回
  2. 如果mid左侧是有序的且nums[begin]<=target<=nums[mid]，那么目标值在mid左侧
  3. 如果mid左侧是有序的且taget不在[nums[begin],nums[mid]]范围内，那么目标值在mid右侧
  4. 如果mid右侧是有序的且nums[mid]<target<=nums[end]，那么目标值在mid右侧
  5. 如果mid右侧是有序的且target不在(nums[mid],nums[end]]，那么目标值在mid左侧。

java代码:

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null || nums.length==0) {
            return -1;
        }
        int begin = 0;
        int end = nums.length-1;
        while(begin<=end) {
            int mid = begin+(end-begin)/2;
            //找到目标值了直接返回
            if(nums[mid]==target) {
                return mid;
            }
            //如果左侧是有序的
            if(nums[begin]<=nums[mid]) {
                //同时target在[ nums[begin],nums[mid] ]中，那么就在这段有序区间查找
                if(nums[begin]<=target && target<=nums[mid]) {
                    end = mid-1;
                //否则去反方向查找	
                } else {
                    begin = mid+1;
                }
            }
            //如果右侧是有序的
            else {
                //同时target在 ( nums[mid],nums[end] ]中，那么就在这段有序区间查找
                if(nums[mid]<target && target<=nums[end]) {
                    begin = mid+1;
                //否则去反方向查找	
                } else {
                    end = mid-1;
                }
            }
        }
        return -1;
    }
}

python代码:

class Solution(object):
    def search(self, nums, target):
        if not nums:
            return -1
        begin = 0
        end = len(nums)-1
        while begin<=end:
            mid = begin+(end-begin)/2
            # 找到目标值了直接返回
            if nums[mid]==target:
                return mid
            # 如果左侧是有序的	
            if nums[begin]<=nums[mid]:
                # 同时target在[ nums[begin],nums[mid] ]中
                # 那么就在这段有序区间查找
                if nums[begin]<=target<=nums[mid]:
                    end = mid-1
                # 否则去反方向查找	
                else:
                    begin = mid+1
            # 如果右侧是有序的		
            else:
                # 同时target在 ( nums[mid],nums[end] ]中
                # 那么就在这段有序区间查找
                if nums[mid]<target<=nums[end]:
                    begin = mid+1
                # 否则去反方向查找	
                else:
                    end = mid-1;
        return -1

解法二变形

代码和解法二几乎是一样的，只在循环中的判断稍稍不同。
其查找过程如下:

  1. 如果nums[mid]==target，找到目标值直接返回
  2. 如果mid右侧是有序的且nums[mid]<=target<=nums[end]，那么目标值在mid右侧
  3. 如果mid右侧是有序的且taget不在[nums[mid],nums[end]]范围内，那么目标值在mid左侧
  4. 如果mid左侧是有序的且nums[begin]<target<nums[mid]，那么目标值在mid左侧
  5. 如果mid左侧是有序的且target不在[nums[begin],nums[mid])，那么目标值在mid右侧。

java代码:

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

python代码:

class Solution(object):
    def search(self, nums, target):
        if not nums:
            return -1
        begin = 0
        end = len(nums)-1
        while begin<=end:
            mid = begin+(end-begin)/2
            if nums[mid]==target:
                return mid
            if nums[mid]<=nums[end]:
                if nums[mid]<=target<=nums[mid]:
                    begin = mid+1
                else:
                    end = mid-1
            else:
                if nums[begin]<=target<nums[mid]:
                    end = mid-1
                else:
                    begin = mid+1
        return -1

(全文完)

2 次阅读

发表评论

电子邮件地址不会被公开。