题目地址
https://leetcode.com/problems/search-in-rotated-sorted-array/
题目描述
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).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
思路
这是一个我在网上看到的前端头条技术终面的一个算法题。
题目要求时间复杂度为logn,因此基本就是二分法了。 这道题目不是直接的有序数组,不然就是easy了。
首先要知道,我们随便选择一个点,将数组分为前后两部分,其中一部分一定是有序的。
具体步骤:
- 我们可以先找出mid,然后根据mid来判断,mid是在有序的部分还是无序的部分
假如mid小于start,则mid一定在右边有序部分。
假如mid大于等于start, 则mid一定在左边有序部分。
注意等号的考虑
- 然后我们继续判断target在哪一部分, 我们就可以舍弃另一部分了
我们只需要比较target和有序部分的边界关系就行了。 比如mid在右侧有序部分,即[mid, end]
那么我们只需要判断 target >= mid && target <= end 就能知道target在右侧有序部分,我们就
可以舍弃左边部分了(start = mid + 1), 反之亦然。
我们以([6,7,8,1,2,3,4,5], 4)为例讲解一下:
关键点解析
- 二分法
- 找出有序区间,然后根据target是否在有序区间舍弃一半元素
代码
- 语言支持: Javascript,Python3
/* * @lc app=leetcode id=33 lang=javascript * * [33] Search in Rotated Sorted Array */ /** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) { // 时间复杂度:O(logn) // 空间复杂度:O(1) // [6,7,8,1,2,3,4,5] let start = 0; let end = nums.length - 1; while (start <= end) { const mid = start + ((end - start) >> 1); if (nums[mid] === target) return mid; // [start, mid]有序 // ️⚠️注意这里的等号 if (nums[mid] >= nums[start]) { //target 在 [start, mid] 之间 // 其实target不可能等于nums[mid], 但是为了对称,我还是加上了等号 if (target >= nums[start] && target <= nums[mid]) { end = mid - 1; } else { //target 不在 [start, mid] 之间 start = mid + 1; } } else { // [mid, end]有序 // target 在 [mid, end] 之间 if (target >= nums[mid] && target <= nums[end]) { start = mid + 1; } else { // target 不在 [mid, end] 之间 end = mid - 1; } } } return -1; };
Python3 Code:
class Solution: def search(self, nums: List[int], target: int) -> int: """用二分法,先判断左右两边哪一边是有序的,再判断是否在有序的列表之内""" if len(nums) <= 0: return -1 left = 0 right = len(nums) - 1 while left < right: mid = (right - left) // 2 + left if nums[mid] == target: return mid # 如果中间的值大于最左边的值,说明左边有序 if nums[mid] > nums[left]: if nums[left] <= target <= nums[mid]: right = mid else: # 这里 +1,因为上面是 <= 符号 left = mid + 1 # 否则右边有序 else: # 注意:这里必须是 mid+1,因为根据我们的比较方式,mid属于左边的序列 if nums[mid+1] <= target <= nums[right]: left = mid + 1 else: right = mid return left if nums[left] == target else -1LeetCode题解215.kth-largest-element-in-an-array
题目地址 https://leetcode.com/problems/kth-largest-element-in-an-array/ 题目描述 Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted or…
LeetCode题解167.two-sum-ii-input-array-is-sorted题目地址 https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/ 题目描述 这是leetcode头号题目two sum的第二个版本,难度简单。 Given an array of integers that is already sorted in ascendi…
LeetCode题解26.remove-duplicates-from-sorted-array题目地址 https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/ 题目描述 Given a sorted array nums, remove the duplicates in-place such that each element appear onl…
bulit-in gradle插件的版本号是多少? - java在我的gradle构建文件中,我有以下插件块plugins { `java-library` jacoco checkstyle } 这些都没有指定版本,但是一切正常。假定一个项目正在使用gradle 6.0和gradle包装器,但是系统已安装gradle 5.0。问题:如果我运行gradle wrapper ./gradlew build,将会执行grad…
LeetCode题解1104.path-in-zigzag-labelled-binary-tree题目地址 https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/description/ 题目描述 在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。 如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标…