[路飞]_leetcode-81-搜索旋转排序数组 II

「这是我参与2022首次更文挑战的第28天，活动详情查看：2022首次更文挑战」

[题目地址][B站地址]

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 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
复制代码

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

进阶：

• 这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
• 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

解题思路

本题最简单的办法就是一趟从头到尾的扫描，如果过程中发现某个元素等于目标值

target，则返回 true，否则返回 false。

当然还有一个取巧的办法，利用数组的 indexOf() 方法判断 nums.indexOf(target) 是否等于 -1。

接下来我们讲另外一种思路：

根据题意，输入数组 nums 是一个升序的数组，只不过在某个下标 k 处进行了翻转，导致前半部分和后半部分分别有序，而且前半部分大于后半部分。

而如果 target 小于此时的 nums[0] 的话，则如果 target 存在，肯定在后半部分，我们只需要在后半部分找。

反之，则如果 target 存在，肯定在前半部分，我们只需要在前半部分找。

代码实现

var search = function (nums, target) {
  // 如果 target 比第一个数字小，则如果存在，会在后半部分
  if (nums[0] > target) {
    for (let i = nums.length - 1; i >= 0; i--) {
      if (nums[i] === target) return true
      // 如果到了前半部分或者下标0位置还没找到，则一定不存在，返回 false
      if ((i > 0 && nums[i - 1] > nums[i]) || i === 0) return false
    }
  } else {
    // 如果 target 大于等于第一个数字，则如果存在，会在前半部分
    for (let i = 0; i < nums.length; i++) {
      if (nums[i] === target) return true
      // 如果到了后半部分或者数组末尾还没找到，则一定不存在，返回 false
      if ((i < nums.length - 1 && nums[i] > nums[i + 1]) || i === nums.length - 1) return false
    }
  }
}
复制代码

至此我们就完成了 leetcode-81-搜索旋转排序数组 II

如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻