LeetCode 33,在不满足二分的数组内使用二分的方法

本文始发于个人公众号:TechFlow,原创不易,求个关注

链接

Search in Rotated Sorted Array

难度

Medium

描述

给定一个升序排列的数组,它被分成两部分之后交换了顺序。要求给定一个元素,返回这个元素的在数组当中的下标,如果不存在返回-1. 时间复杂度必须是(O(logn))

Suppose an array sorted in ascending order is rotated at some pivot unknown to
you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its
index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O (log n ).

样例 1:

Input: nums = [4,5,6,7,0,1,2], target = 0  Output: 4

样例 2:

Input: nums = [4,5,6,7,0,1,2], target = 3  Output: -1

题解

这题非常明显,虽然看似限制了时间复杂度在提升难度,但其实是在给大家提示。一个数组查找元素,时间复杂度还是(log(n)),这显然是在暗示大家什么。我想大家作为一个成熟的程序员,异性的暗示未必读的懂,但来自出题人的暗示一定能get到【狗头】。

显然,这题需要使用二分法,但是如何使用二分呢,这才是本题的重点。

两次二分

第一种方法非常简单粗暴,因为我们已经知道要二分查找了,然后我们还知道数组分成了两截之后又交换了顺序。所以数组的情况应该是这样的:

对不起,我画得有些抽象,但是精髓传达到了。什么意思呢?就是原本升序的数组分成了两截之后交换顺序,那么现在的数组应该是两端递增的序列拼接构成的。既然是两端序列,那么中间显然有一个断点。我们只要找到这个断点的位置,就容易了,这个问题就变成了在两个有序的数组里查找元素了,那就没有难度了。

但是这个断点怎么找呢?

显然不是打开QQ音乐,而是要使用二分法。因为前面我们已经说了,我们整体的复杂度是log级的,显然我们不可能用遍历来寻找断点。留给我们的就只有一条路,就是二分。

设计这里的二分需要对二分法有一定深入的了解,因为在这个问题当中其实是不满足二分法的使用条件的,因为数组被分成了两个部分,已经不是整体有序了。但是虽然不是整体有序,但仍然是有办法的。

我们先来根据上面的图来分析一下,很容易发现,断点的位置就是全局最小值。我们可以找到左侧部分的最大值,或者是右侧部分的最小值,就是断点的位置。

我们再来分析一下二分时候可能出现的情况,一开始的时候l在最左侧,r在最右侧,m则是两侧都有可能。如果m在左侧部分,那么m位置的值一定大于l,否则一定小于l。所以我们通过比较m和l位置元素的大小关系可以判断m在左侧还是右侧。

如果说我们最终的搜索目标是寻找左侧部分的最大值,那么当m处的值大于l时,则舍弃左侧部分,因为左侧部分已经不可能是答案了。同理,如果m处的值小于l,那么应该舍弃m右侧,因为m右侧都在右边部分,当中是不可能有左侧部分的最大值的,通过这种方法我们也可以使用二分查找,只不过条件和我们常用的二分不太一样。

def binary_search(arr):      l, r = 0, len(arr)      while r - l > 1:          m = (l + r) >> 1          if arr[m] > arr[l]:              l = m          else:              r = m      return l

找到断点之后就容易了,就是简单的无脑二分了。我们来看代码:

class Solution:      def search(self, nums: List[int], target: int) -> int:          # 找到断点          l, r = 0, len(nums)          if r == 0:              return -1            while r - l > 1:              m = (l + r) >> 1              if nums[m] > nums[l]:                  l = m              else:                  r = m            # 根据target和第0个元素比较大小判断target在左还是右          if target < nums[0]:              l, r = r, len(nums)          else:              l, r = 0, l+1            if l == len(nums):              return -1            # 二分查找          while r - l > 1:              m = (l + r) >> 1              if nums[m] <= target:                  l = m              else:                  r = m          return l if nums[l] == target else -1

一次二分

虽然我们三下五除二地解决了问题,但是我仍然不够满意,总觉得这种做法不够巧妙,应该还能继续优化。比如说我们能不能不先找断点的位置直接二分呢?

仔细想的话是可以的,尤其是我们已经有了上面这种做法的情况下。

在我们上面查找断点的时候,已经有了一个重要的关键信息,就是我们可以通过m和l位置比大小来确定断点在什么位置。既然我们可以确定断点的位置,那么我们同样可以确定target的位置。

说起来很抽象,我们来看图:

这是一种情况,即m的位置在断点右侧,也就是右侧。那么我们通过判断target和l处的大小关系可以判断target可能在哪个部分。

如果target > nums[l],那么显然target在左侧,所以我们应该让r=m,即抛弃右部分。

如果target < nums[l],这个时候还不能确定范围。因为m左侧可能还有比m小的元素,所以我们还需要判断一下target和nums[m]的关系,来判断抛弃哪个部分。如果target < nums[m],那么抛弃右部分,否则抛弃左部分。

下面来看第二种情况:

同样我们判断target和nums[l]的关系,如果target > nums[l],那么我们需要继续判断它和m的关系,来决定抛弃哪个部分。如果target < nums[l],那么说明我们需要抛弃m左侧的部分。

情况虽然有点复杂,但是我们画个图还是很容易理清楚的。一旦理清楚了,我们就可以一次二分搞定全局。

来看代码:

class Solution:      def search(self, nums: List[int], target: int) -> int:          if len(nums) == 0:              return -1            l, r = 0, len(nums)            while r - l > 1:              m = (l + r) >> 1              # 如果m出现做左侧部分              if nums[m] >= nums[l]:                  if target >= nums[l]:                      if target < nums[m]:                          r = m                      else:                          l = m                  # 如果target小于nums[l],需要让l=m+1,因为m这个点也是非法点                  else:                      l = m+1              else:                  if target >= nums[l]:                      r = m                  else:                      if target >= nums[m]:                          l = m                      else:                          r = m          return l if l < len(nums) and nums[l] == target else -1

到这里整个题目就分析完了,但是比较搞笑的是虽然我们第二种算法看起来牛哄哄,减少了一次二分,但是提交上去之后的结果反而耗时要长一些。而且相信大家也感觉到了,这种方法实现起来要复杂得多,边界条件很容易写错。所以这点告诉我们一个道理,厉害的方法不一定效果好。

这道题虽然不难,但是挺有意思,打破了我们一直以来对于二分法的认识,不知道会不会给你们带来脑洞大开的感觉。

今天的文章就是这些,如果觉得有所收获,请顺手点个关注吧,你们的举手之劳对我来说很重要。