链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/
1.求平方根,精度到小数点后10位
实现 int sqrt(int x) 函数。 leetcode 69 计算并返回 x 的平方根，其中 x 是非负整数。
- 左右指针使用double
结束条件变为 left + 0.0000000001 < right ```java public class Solution { double threshold = 0.00000000001;
public int mySqrt(int x) {
// 特殊值判断if (x == 0) {return 0;}if (x == 1) {return 1;}double left = 1;double right = x;// 在区间 [left..right] 查找目标元素while (left + threshold < right) {double mid = left + (right - left ) / 2;// 注意：这里为了避免乘法溢出，改用除法if (mid > x / mid) {right = mid ;} else {left = mid;}}return left;
} }
<a name="oNZ7w"></a>
### 2.两个正序数组中位数
---
> 给定两个大小分别为 m 和 n 的正序（从小到大）数组 , 请你找出并返回这两个正序数组的**中位数** 。 [**leetcode 4**](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)
```java
输入：nums1 = [1,3], nums2 = [2] 输入：nums1 = [1,2], nums2 = [3,4]
输出：2.00000 输出：2.50000
解释：合并数组 = [1,2,3], 中位数2 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
- 中位数位置：
- 当数组的总长度为偶数的时候，分割线左右的数字个数总和相等；
- 当数组的总长度为奇数的时候，分割线左数字个数比右边仅仅多 1；
- 分割线左边的所有元素都小于等于（不大于）分割线右边的所有元素
- 在一个数组中二分查找 i ，另一个数组索引值为 (m + n + 1) / 2 - i ；
分割线左侧元素小于等于分割线右侧元素。由于两个数组均为正序数组，则只需要要求：nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]；由于该条件等价于在[0, m]中找到最大的i使得nums1[i-1] <= nums2[j]，因此可以使用二分查找。
- 特殊情况：
在短数组上搜索边界 i ，可能遇到 i 或者 j 的左边或者右边取不到元素的情况，它们一定出现在退出循环的时候。需要单独做判断。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 始终保证nums1为较短的数组，nums1过长可能导致j为负数而越界
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
// m+n 为奇数，分割线要求左侧有 (m+n)/2 + 1 个元素
// m+n 为偶数，分割线要求左侧有 (m+n)/2 个元素
// 两种情况其实可以统一写作 (m+n+1)/2，表示对(m+n)/2向上取整
int leftTotal = (m + n + 1) / 2;
int left = 0, right = m;
while (left < right) {
// +1 向上取整避免 left + 1 = right 时可能无法继续缩小区间而陷入死循环
int i = left + (right - left + 1) / 2;
int j = leftTotal - i;
//要找最大i，使得nums1[i-1] <= nums2[j]
//使用对立面缩小区间
if (nums1[i - 1] > nums2[j]) {
// [i+1, m]均不满足
right = i - 1;
} else {
// i满足说明[0, i-1]均不为满足条件的最大i，舍去以缩小区间
left = i;
}
}
//退出循环时left=right，表示最终nums1中分割线的位置
int i = left;
//nums2中分割线的位置
int j = leftTotal - left;
System.out.println(i);
//判断极端情况
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; //nums1分割线左边没有元素
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; //nums2分割线左边没有元素
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i]; //nums1分割线右边没有元素
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j]; //nums2分割线右边没有元素
if ((m + n) % 2 == 0) {
return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
} else {
return Math.max(nums1LeftMax, nums2LeftMax);
}
}
}
3.搜索(重复)排序旋转数组
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
输入：nums = [4,5,6,7,0,1,2], target = 0 输入：nums = [4,5,6,7,0,1,2], target = 3 输出：4 输出：-1
public int search(int[] nums, int target) {
if(nums.length == 1) return nums[0] == target ? 0 : -1;
int left = 0;
int right = nums.length - 1;
//寻找拐点
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] < nums[right]){
right = mid;
}else if(nums[mid] > nums[right]){
left = mid + 1;
}else{ //去重
right--;
}
}
if(left == 0){ //数组没有旋转，从小到大排列
right = nums.length;
}else{
if(nums[0] <= target){ // target在左边
left = 0;
}else{
right = nums.length; // target在右边
}
}
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] > target){
right = mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
4.最大(小)值最小(大)化
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。 leetcode 410
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）leetcode 875
5.搜索左右边界
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 leetcode 34
左边界
- 取值区间是闭区间[0, nums.length]，所以需要判断边界。
if (left == nums.length) return -1; target 比所有数都大
nums[left] == target ? left : -1;右边界
我们对left的更新必须是left = mid + 1，就是说 while 循环结束时，nums[left]一定不等于target了，而nums[left-1]可能是target。
- if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length;
int[] res = new int[2];
Arrays.fill(res,-1);
if(nums.length == 0) return res;
// 左边界 left 取值 [0,num.length]
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1;
}else{
right = mid;
}
}
if(left < nums.length && nums[left] == target){
res[0] = left;
}
left = 0;
right = nums.length;
// 右边界
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] <= target){
left = mid + 1;
}else{
right = mid;
}
}
if(left >= 1 && nums[left - 1] == target){
res[1] = left - 1;
}
return res;
}
}
若有收获，就点个赞吧
0 人点赞
