网站搭建流程图,济南网站建设vashine,长春专业做网站的公司排名,树莓派wordpress建站习题1
704. 二分查找
给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。
示例 1:
输入: nums [-1,0,3,5,9,12], targ…习题1
704. 二分查找
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
示例 1:
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums [-1,0,3,5,9,12], target 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1提示
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
写法1
class Solution {public int search(int[] nums,int target) {if(target nums[0] || target nums[nums.length - 1]) {return -1;}int left 0;int right nums.length - 1;while(left right) {int mid left (right - left) / 2;if(nums[mid] target) {right mid - 1;}else if (nums[mid] target) {left mid 1;}else {return mid;}}return -1;}
}
上述写法为第一种写法我们定义的target所在的区间是一个左闭右闭的区间也就是[left,right]
区间的定义决定了二分法该如何写此写法target在[left,right]区间有以下特点
1. while (left right) 要使用 因为left right 是有意义的故要使用
2. if (nums[middle] target) right 要赋值为 middle - 1因为当前这个nums[middle] 一定不是target那么接下来要查找的做区间结束下标位置就是 middle - 1left 赋值 middle 1 同理。 写法2
class Solution {public int search(int[] nums , int target) {if(target nums[0] || target nums[nums.length - 1]) {return -1;}int left 0;int right nums.length;while(left right) {int mid left (right - left) / 2;if(nums[mid] target) {left mid 1;}else if(nums[mid] target) {right mid;}else {return mid;}}return -1;}
} 该写法则是将target定义在一个左闭右开的区间中也就是[left,right)此时二分法的边界处理就截然不同
1. while(left right),这里使用 ,因为left right 在区间 [left,right) 是没有意义的.
2. if(nums[mid] target) right 更新为mid,因为当前nums[mid] 不等于target,去做区间继续寻找,而寻找区间是左闭右开区间,所以right 更新为 mid,而左边界是闭区间,则if(nums[mid] target) 中,left 更新为 mid 1. 以下题目均由二分法第一种写法实现 习题2
35. 搜索插入位置
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。 示例 1:
输入: nums [1,3,5,6], target 5
输出: 2示例 2:
输入: nums [1,3,5,6], target 2
输出: 1示例 3:
输入: nums [1,3,5,6], target 7
输出: 4提示:
1 nums.length 104-104 nums[i] 104nums 为 无重复元素 的 升序 排列数组-104 target 104 这道题目其实就是在二分算法的壳子上面做了些许点缀,根本上还是二分算法的应用,但是多了一些特殊情况的判断,题解如下:
class Solution {public int searchInsert(int[] nums, int target) {int n nums.length;if(target nums[0]) {return 0;}else if(target nums[n - 1]){return n;}int left 0;int right n - 1;while(left right) {int mid left (right - left) / 2;if(nums[mid] target) {right mid - 1;if(nums[right] target) {return mid;}}else if(nums[mid] target) {left mid 1;if(nums[left] target) {return mid 1;}}else {return mid;}}return -1;}
}
从代码实现上不难看出,这其实就是一个二分算法,只不过在特殊情况下做了一些特殊处理,我这里将特殊情况所产生的结果一一进行了返回(有点笨的方法),在处于左侧情况与右侧情况中无法查询到的数据位置重新进行了判断. 习题3
69. x 的平方根
给你一个非负整数 x 计算并返回 x 的 算术平方根 。
由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。
注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1
输入x 4
输出2示例 2
输入x 8
输出2
解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。提示
0 x 231 - 1
class Solution {public int mySqrt(int x) {int left 0;int right x;while(left right) {int mid left (right - left) / 2;if((long)mid * mid x) {left mid 1;if(left * left x) {return mid;}}else if((long)mid * mid x) {right mid - 1;if((long)right * right x) {return right;}}else {return mid;}}return -1;}
}
这道题目相对上面那道题目又多了一些变化.除了如习题2一般要对特殊条件再判断外,还需要考虑if((long)mid * mid x) if中条件的变化,我们需要按照题目所给的比较依据来判断if中的条件.
