LeetCode实战：搜索旋转排序数组
题目英文
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
题目中文
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
示例 3:
输入: nums = [5,1,3], target = 5
输出: 0
示例 4:
输入: nums = [4,5,6,7,8,1,2,3], target = 8
输出: 0
示例 5:
输入: nums = [3,1], target = 1
输出: 1
算法实现
public class Solution {public int Search(int[] nums, int target) {int i = 0, j = nums.Length - 1;while (i <= j){int mid = (i + j) / 2;if (nums[mid] == target)return mid;if (nums[mid] >= nums[i]){//左半部分有序if (target > nums[mid]){i = mid + 1;}else{if (target == nums[i])return i;if (target > nums[i])j = mid - 1;elsei = mid + 1;}}else{if (target < nums[mid]){j = mid - 1;}else{if (target == nums[j])return j;if (target < nums[j])i = mid + 1;elsej = mid - 1;}}}return -1; }
}
实验结果
- 状态：通过
- 196 / 196 个通过测试用例
- 执行用时: 128 ms, 在所有 C# 提交中击败了 97.17% 的用户
- 内存消耗: 23.8 MB, 在所有 C# 提交中击败了 12.00% 的用户
相关图文
1. “数组”类算法
- LeetCode实战：三数之和
- LeetCode实战：最接近的三数之和
- LeetCode实战：求众数
- LeetCode实战：缺失的第一个正数
- LeetCode实战：快乐数
- LeetCode实战：寻找两个有序数组的中位数
- LeetCode实战：盛最多水的容器
2. “链表”类算法
- LeetCode实战：两数相加
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
3. “栈”类算法
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
4. “队列”类算法
- LeetCode实战：设计循环双端队列
- LeetCode实战：滑动窗口最大值
- LeetCode实战：整数反转
- LeetCode实战：字符串转换整数 (atoi)
5. “递归”类算法
- LeetCode实战：爬楼梯
6. “字符串”类算法
- LeetCode实战：反转字符串
- LeetCode实战：翻转字符串里的单词
- LeetCode实战：最长公共前缀
7. “树”类算法
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：将有序数组转换为二叉搜索树
8. “哈希”类算法
- LeetCode实战：两数之和
9. “搜索”类算法
- LeetCode实战：搜索二维矩阵
10. “动态规划”类算法
- LeetCode实战：最长回文子串
11. “数值分析”类算法
- LeetCode实战：回文数
- LeetCode实战：x 的平方根
相关文章：
Python内置数据结构之双向队列
经常听说Python就是一门执行速度低的语言，可能是你的程序中使用了复杂的算法与数据结构，才会导致程序执行速率低的。在Python的标准库中提供了常见的数据结构工开发者使用，不仅执行速率比较快，还可以简化开发者的编程工作。下面我…
C# GDAL 学习一
最近一直琢磨如何用C#GDAL读取栅格数据（.tif或.img），运气不错的在GDAL 的官网上找到一部分源码。经过本人测试，效果还不错。学习还将继续深入下去。 参考网址：http://trac.osgeo.org/gdal/browser/trunk/gdal/swig/csh…
LeetCode实战：字符串相加
题目英文 Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2. Note: The length of both num1 and num2 is < 5100.Both num1 and num2 contains only digits 0-9.Both num1 and num2 does not contain any leadin…
js中修改this的指向方法整理
JavaScript(简称“JS”) 是一种具有函数优先的轻量级，解释型或即时编译型的编程语言。虽然它是作为开发Web页面的脚本语言而出名，但是它也被用到了很多非浏览器环境中，JavaScript 基于原型编程、多范式的动态脚本语言，并且支持面向…
VC运行时库（/MD、/MT等）
VC项目属性→配置属性→C/C→代码生成→运行时库 可以采用的方式有：多线程(/MT)、多线程调试(/MTd)、多线程DLL(/MD)、多线程调试DLL(/MDd)、单线程(/ML)、单线程调试(/MLd)。 Reusable LibrarySwitchLibraryMacro(s) DefinedSingle Threaded/MLLIBC(none)Static Mu…
函数式编程概述
2019独角兽企业重金招聘Python工程师标准>>> 引子 JDK8中引入了lambda函数式编程的概念，那么什么是函数式编程，函数式编程又有什么好处，今天我们就来说说函数式编程 我们先了解一下函数式编程的由来 一个名叫阿隆佐邱奇的数学家设…
LeetCode实战：字符串相乘
题目英文 Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 "2", num2 "3" Output: "6"Example 2: Input: num1 &q…
UI培训教程之系统图标如何设计?
UI设计在近几年广受大家的关注，学习UI设计的人越来也多，今天小编要介绍的就是其中的系统图标设计方法，系统图标在UI设计中是非常基础的图形化语言，也在页面交互中起到很重要的作用。单个图标的设计并不难，但是系统化、…
看懂SQL Server的查询计划(绝对好文！)
在园子看到一篇SQLServer关于查询计划的好文，激动啊,特转载。原文出自:http://www.cnblogs.com/fish-li/archive/2011/06/06/2073626.html看懂SqlServer查询计划对于SqlServer的优化来说，可能优化查询是很常见的事情。关于数据库的优化，本身也…
LeetCode实战：全排列
题目英文 Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]题目中文 给定一个没有重复数字的序列，返回其所有可能的全排列。 示例: 输入: …
git pull出现There is no tracking information for the current branch
使用git pull 或者 git push 的时候报错 gitThere is no tracking information for the current branch. Please specify which branch you want to merge with. See git-pull(1) for details git pull <remote> <branch> If you wish to set tracking information…
零基础快速学习Java技术的方法整理
在学习java技术这条道路上，有很多都是零基础学员，他们对于java的学习有着很多的不解，不知怎么学习也不知道如何下手，其实Java编程涉及到的知识点还是非常多的，我们需要制定java学习路线图这样才能少走弯路，…
转 深入理解Midlet类
在J2ME编程过程中，MIDlet是最核心的类之一，熟悉该类的使用是J2ME学习过程中必须首先掌握的类，下面就结合实际介绍一下该类的实际使用。 众所周知，J2ME程序都是从MIDlet类开始执行，系统规定了MIDlet的生命周期。规定MID…
LeetCode实战：最大子序和
题目英文 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum 6.Follow up…
PHP如何更好的利用PHPstorm的自动提示
说明 写了一段时间的java之后，特别不习惯PHP本身的弱类型方式，在写代码的时候总觉得不怎么放心，特别本身PHP又是弱类型的语言，所以在编码的时候，很多时候是没有代码提示的。 一个一般例子 class Data {public $name;pu…
2021年Java面试题目最新总结【90%面试会踩的坑】
学会java技术之后大家面临的最多的问题就是面试这关，求职面试java岗位是否能够成功是直接影响我们的工作机会的，所以对于Java程序员面试你准备好了吗?今天小编汇总了一下关于Java程序员面试，90%会踩到的坑。 2021年Java面试题目最新总结【90…
LeetCode实战：螺旋矩阵
题目英文 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. Example 1: Input: [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5]Example 2: Input: [[1, 2, 3, 4],[5, 6, 7, 8],[9,10,11,…
Json的序列化和反序列化
1、引用命名空间: usingSystem.Runtime.Serialization;2、json的序列化和反序列化的方法： publicclassJsonHelper {///<summary>///序列化///</summary>///<typeparam name"T"></typeparam>///<param name"t">&l…
Angular开山篇
1：环境搭建 今天给大家介绍4种环境搭建的方法。一：Angular-cli的安装 官方指导文档：www.angular.cn/guide/quickstart 请使用cnpm来安装，或者配置淘宝镜像。 使用原生npm安装可能会遇到的问题： 需要python的环境可能会…
零基础参加软件测试培训需要学多长时间
软件测试对于零基础学员来说是非常好入门的，软件测试没有很多的限制，那么零基础参加软件测试培训需要学多长时间呢?来看看下面的详细介绍吧。 零基础参加软件测试培训需要学多长时间?软件测试培训时间一般都在四个月左右，四个月时间的课程内…
Windows API函数大全
1. API之网络函数 WNetAddConnection 创建同一个网络资源的永久性连接 WNetAddConnection2 创建同一个网络资源的连接 WNetAddConnection3 创建同一个网络资源的连接 WNetCancelConnection 结束一个网络连接 WNetCancelConnection2 结束一个网络连接 WNetCloseEnum 结束一…
LeetCode实战：螺旋矩阵 II
题目英文 Given a positive integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order. Example: Input: 3 Output: [[ 1, 2, 3 ],[ 8, 9, 4 ],[ 7, 6, 5 ] ]题目中文 给定一个正整数 n，生成一个包含 1 到 n^2 所有元素&#x…
电子文件归档为什么非云不可
本文讲的是电子文件归档为什么非云不可华为云为企业搭建功能强大的电子文件归档系统平台，一站式满足文件存储与管理、协同分享、移动办公等不同的业务需求。打造安全、高效、便捷的文件归档环境，帮助企业节省运营成本，优化管理流程࿰…
北京学习Java培训有哪些比较好
北上广算是互联网技术大咖的聚集之地，很多知名互联网企业都在这些城市，随之java培训机构也是非常多的，那么在北京学习java培训有哪些比较好呢?来看看下面的详细介绍吧。 北京学习Java培训有哪些比较好?想要在这些培训机构中选择比较靠谱的J…
C#命名规则、开发习惯和风格
1. 文件命名组织 1-1文件命名 1. 文件名遵从Pascal命名法，无特殊情况，扩展名小写。 2. 使用统一而又通用的文件扩展名： C# 类 .cs 1-2文件注释 1. 在每个文件头必须包含以下注释说明 1 在每个文件头必须包含以下注…
LeetCode实战：不同路径
题目英文 A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Fini…
前端部分面试题整理，欢迎补充
1.ng中如何配置路由，$scope和$rootscope的原理ng中如何配置路由?1)使用内置路由模块ng-routevar app angular.module(ngRouteExample, [ngRoute]).controller(MainController, function($scope) {}).config(function($routeProvider, $locationProvider) {$routeP…
JS栈结构的简单封装
栈：是一种遵循后进先出(Last In First Out / LIFO) 原则的一种有序集合。 新添加或者要删除的元素都会保存在栈的同一端，我们把它叫做栈顶，另外一端叫做栈底。 在栈中所有的新元素都接近栈顶，而所有的旧元素都接近栈底。 在我们的…
记录CSS3 target伪类简介
CSS3 target伪类是众多实用的CSS3特性中的一个。它用来匹配文档(页面)的URI中某个标志符的目标元素。具体来说，URI中的标志符通常会包含一个”#”字符，然后后面带有一个标志符名称，比如#respond，target就是用来匹配ID为respond的元…
LeetCode实战：合并两个有序数组
题目英文 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively.You may assume that nums1 has enough space (size that is greater o…