原题
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例1：
输入： [3,4,5,1,2] 输出： 1
示例2：
输入： [4,5,6,7,0,1,2] 输出： 0
解法
思想
- 线性查找
- 二分查找，找出旋转点
代码
- 线性查找
class Solution {
public int findMin(int[] nums) {
int min = nums[0];
for(int i:nums){
if(i<min){
min=i;
break;
}
}
return min;
}
}
- 二分查找
class Solution {
public int findMin(int[] nums) {
int head = nums[0];
int start = 0;
int end = nums.length-1;
while(start<end){
int mid = start + (end-start)/2;
if(nums[mid] >= head) start = mid+1;
else if(nums[mid] < head) end = mid;
}
if(nums[start]>head) return head;
return nums[start];
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode153-%e5%af%bb%e6%89%be%e6%97%8b%e8%bd%ac%e6%8e%92%e5%ba%8f%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e6%9c%80%e5%b0%8f%e5%80%bc/
相关推荐
-
leetcode485-最大连续1的个数
原题 给定一个二进制数组， 计算其中最大连续1的个数。 示例 1: 输入： [1,1,0,1,1,1] 输出： 3 解释： 开头的两位和最后的三位都是连续1，所以最大连续1的个数是...
-
leetcode22-括号生成
原题 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入：n = 3 输出：[ "((()))", "(()())", "...
-
leetcode331-验证二叉树的前序序列化
原题 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。 _9_ / \ 3 2...
-
剑指offer05-替换空格
原题（来源Leetcode） 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例1: 输入： s = "We are happy." 输出： "We%20are%2...
-
leetcode836-矩形重叠
原题 矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。 如果相交的面积为正，则称两矩形重叠。需要...
-
leetcode217-存在重复元素
原题 给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。 示例1： 输入： [1,2,3...
-
leetcode63-不同路径II
原题 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi...
-
leetcode134-加油站
原题 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[...
-
leetcode376-摆动序列
原题 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,...
-
leetcode990-等式方程的可满足性
原题 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a...
