C++实现LeetCode(81.在旋转有序数组中搜索之二)
[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0Example 2:
Output: true
【C++实现LeetCode(81.在旋转有序数组中搜索之二)】Input: nums = [2,5,6,0,0,1,2], target = 3Follow up:
Output: false
- This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
- Would this affect the run-time complexity? How and why?
class Solution {public:bool search(vector& nums, int target) {int n = nums.size(), left = 0, right = n - 1; while (left <= right) {int mid = (left + right) / 2; if (nums[mid] == target) return true; if (nums[mid] < nums[right]) {if (nums[mid] < target && nums[right] >= target) left = mid + 1; else right = mid - 1; } else if (nums[mid] > nums[right]){if (nums[left] <= target && nums[mid] > target) right = mid - 1; else left = mid + 1; } else --right; }return false; }};
到此这篇关于C++实现LeetCode(81.在旋转有序数组中搜索之二)的文章就介绍到这了,更多相关C++实现在旋转有序数组中搜索之二内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- python|python pygame实现五子棋双人联机
- C++详解多线程中的线程同步与互斥量
- 数据结构(c语言实现)|<数据结构>还不会写单向链表(我手把手教你)
- 数据结构(c语言实现)|<数据结构>刷题笔记——链表篇(一)(有动图详解)
- Android 桌面悬浮窗效果实现,仿360手机卫士悬浮窗效果
- Android 类似360悬浮窗口实现源码
- 安卓手机端实现点击电话号码,出现拨打复制保存到通讯录
- 数据结构|排序算法之希尔排序——c++实现
- 算法|希尔排序——JS实现
- 手撕常用排序算法|希尔排序——C语言实现