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 = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

  • 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?

这道是之前那道 Search in Rotated Sorted Array 的延伸,现在数组中允许出现重复数字,这个也会影响我们选择哪半边继续搜索,由于之前那道题不存在相同值,我们在比较中间值和最右值时就完全符合之前所说的规律:如果中间的数小于最右边的数,则右半段是有序的,若中间数大于最右边数,则左半段是有序的。而如果可以有重复值,就会出现来面两种情况,[3 1 1] 和 [1 1 3 1],对于这两种情况中间值等于最右值时,目标值3既可以在左边又可以在右边,那怎么办么,对于这种情况其实处理非常简单,只要把最右值向左一位即可继续循环,如果还相同则继续移,直到移到不同值为止,然后其他部分还采用 Search in Rotated Sorted Array 中的方法,可以得到代码如下:

class Solution {
public:
    bool search(vector<int>& 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++实现在旋转有序数组中搜索之二内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-17

C++实现LeetCode(75.颜色排序)

[LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2

C++实现LeetCode(79.词语搜索)

[LeetCode] 79. Word Search 词语搜索 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. Th

C++实现LeetCode(76.最小窗口子串)

[LeetCode] 76. Minimum Window Substring 最小窗口子串 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BA

C++实现LeetCode(82.移除有序链表中的重复项之二)

[LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Outp

C++实现LeetCode(80.有序数组中去除重复项之二)

[LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus

C++实现LeetCode(72.编辑距离)

[LeetCode] 72. Edit Distance 编辑距离 Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a char

C++实现LeetCode(74.搜索一个二维矩阵)

[LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

C++实现LeetCode(73.矩阵赋零)

[LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably

浅谈c/c++中使用指针需要注意的问题

一.使用指针的时候需要注意几点: • 分配空间 • 初始化 • 释放 二.常见的错误有几种: 1)内存分配未成功,却使用了它 编程新手常犯这种错误,因为他们没有意识到内存分配会不成功.常用解决办法是,使用内存之前检查指针是否为Null. 如果指针p是函数的参数,那么在函数的入口处用assert(p != NULL)进行检查.如果使用malloc或new来申请内存,应该用if(p == NULL)或if(p != NULL)进行放错处理. 2)内存分配虽然成功,但是尚未初始化就引用它 犯这种错误主

浅谈C++内存分配及变长数组的动态分配

第一部分 C++内存分配 一.关于内存 1.内存分配方式 内存分配方式有三种: (1)从静态存储区域分配.内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在 例如全局变量,static变量. (2)在栈上创建.在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存 储单元自动被释放.栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限. (3) 从堆上分配,亦称动态内存分配.程序在运行的时候用malloc或new申请任意多少的内存,程序员

老生常谈C/C++内存管理

内存分配方式 简介 在C++中,内存分成5个区,他们分别是堆.栈.自由存储区.全局/静态存储区和常量存储区. 栈:在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放.栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限. 堆:就是那些由 new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个 delete.如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收. 自由存储区:就是那些由mall

Opencv2.4.9函数HoughLinesP分析

标准霍夫变换本质上是把图像映射到它的参数空间上,它需要计算所有的M个边缘点,这样它的运算量和所需内存空间都会很大.如果在输入图像中只是处理m(m<M)个边缘点,则这m个边缘点的选取是具有一定概率性的,因此该方法被称为概率霍夫变换(Probabilistic Hough Transform).该方法还有一个重要的特点就是能够检测出线端,即能够检测出图像中直线的两个端点,确切地定位图像中的直线. HoughLinesP函数就是利用概率霍夫变换来检测直线的.它的一般步骤为: 1.随机抽取图像中的一个特

python 判断矩阵中每行非零个数的方法

如下所示: # -*- coding: utf-8 -*- # @Time : 2018/5/17 15:05 # @Author : Sizer # @Site : # @File : test.py # @Software: PyCharm import time import numpy as np # data = np.array([ # [5.0, 3.0, 4.0, 4.0, 0.0], # [3.0, 1.0, 2.0, 3.0, 3.0], # [4.0, 3.0, 4.0,

Bootstrap零基础入门教程(三)

什么是 Bootstrap? Bootstrap 是一个用于快速开发 Web 应用程序和网站的前端框架.Bootstrap 是基于 HTML.CSS.JAVASCRIPT 的. 历史 Bootstrap 是由 Twitter 的 Mark Otto 和 Jacob Thornton 开发的.Bootstrap 是 2011 年八月在 GitHub 上发布的开源产品. 写到这里,这篇从零开始学Bootstrap(3)我想写以下几个内容: 1. 基于我对Bootstrap的理解,做一个小小的总结.

Python实现的矩阵类实例

本文实例讲述了Python实现的矩阵类.分享给大家供大家参考,具体如下: 科学计算离不开矩阵的运算.当然,python已经有非常好的现成的库:numpy(numpy的简单安装与使用可参考http://www.jb51.net/article/66236.htm). 我写这个矩阵类,并不是打算重新造一个轮子,只是作为一个练习,记录在此. 注:这个类的函数还没全部实现,慢慢在完善吧. 全部代码: import copy class Matrix: '''矩阵类''' def __init__(sel

PHP简单实现二维数组的矩阵转置操作示例

本文实例讲述了PHP简单实现二维数组的矩阵转置操作.分享给大家供大家参考,具体如下: <?php $arr1 = array( array(1,2,3), array(4,5,6), array(6,7,8), array('a','b','c') ); echo '我们测试结果:<br><br>'; echo '矩阵转置前:<br>'; for($i=0;$i<count($arr1);$i++){ for($j=0;$j<count($arr1[$

JS使用贪心算法解决找零问题示例

本文实例讲述了JS使用贪心算法解决找零问题.分享给大家供大家参考,具体如下: 前面介绍了JS贪心算法解决背包问题,这里再来看看找零问题的解决方法. 在现实生活中,经常遇到找零问题,假设有数目不限的面值为20,10,5,1的硬币. 给出需要找零数,求出找零方案,要求:使用数目最少的硬币. 对于此类问题,贪心算法采取的方式是找钱时,总是选取可供找钱的硬币的最大值.比如,需要找钱数为25时,找钱方式为20+5,而不是10+10+5. 贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很

python中numpy的矩阵、多维数组的用法

1. 引言 最近在将一个算法由matlab转成python,初学python,很多地方还不熟悉,总体感觉就是上手容易,实际上很优雅地用python还是蛮难的.目前为止,觉得就算法仿真研究而言,还是matlab用得特别舒服,可能是比较熟悉的缘故吧.matlab直接集成了很多算法工具箱,函数查询.调用.变量查询等非常方便,或许以后用久了python也会感觉很好用.与python相比,最喜欢的莫过于可以直接选中某段代码执行了,操作方便,python也可以实现,就是感觉不是很方便. 言归正传,做算法要用