这个系列的题可以说是秒掉,只要记住这个模板,同时要理解边界问题就好了.如果你要找左节点,mid就是l + r >> 1
,如果你要找右节点,那么mid就是l + r + 1 >> 1
,因为除于2的时候会四舍五入。我给的模板是找左节点的
int l = 0 , r = nums.length - 1;
while(l < r) {
int mid = l + r >> 1;
if(target <= nums[mid]) r = mid;
else l = mid + 1;
}
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1, f = -1;
while(l < r) {
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[l] == target) return l;
else if(nums[l] < target) return r + 1;
else return r;
}
}
给你一个满足下述两条属性的 m x n
整数矩阵:
target
,如果 target
在矩阵中,返回 true
;否则,返回 false
。输入: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出: true
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int m = matrix[0].length;
int idx = 0;
int[] nums = new int[n * m];
for(int i = 0;i < n;i ++) {
for(int j = 0;j < m;j ++){
nums[idx ++] = matrix[i][j];
}
}
int l = 0 , r = n * m - 1;
while(l < r) {
int mid = l + r >> 1;
if(target <= nums[mid]) r = mid;
else l = mid + 1;
}
if(nums[l] == target) return true;
else return false;
}
}
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
class Solution {
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
if(n == 0) return new int[]{-1, -1};
int l = 0, r = n - 1;
while(l < r) {
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
System.out.println(l);
if(nums[l] != target) return new int[]{-1, -1};
else r = n - 1;
int[] ans = new int[2];
ans[0] = l;
while(l < r) {
int mid = l + r + 1>> 1;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
ans[1] = r;
return ans;
}
}
整数数组 nums
按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7]
在下标 3
处经旋转后可能变为 [4,5,6,7,0,1,2]
。
给你 旋转后 的数组 nums
和一个整数 target
,如果 nums
中存在这个目标值 target
,则返回它的下标,否则返回 -1
。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 1) {
if (target == nums[0]) return 0; // 如果数组长度为1且目标值与唯一元素相等,返回0
else return -1; // 否则返回-1,表示未找到目标值
}
int rever = 0;
// 找到旋转点的索引
for (int i = 1; i < n; i++) {
if (nums[i] < nums[i - 1]) {
rever = i;
}
}
int l = 0, r;
// 根据旋转点的位置设置右边界
if (rever != 0) {
r = rever - 1;
} else {
r = n - 1;
}
// 在前半段查找目标值
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
// 检查是否找到目标值
if (target > nums[l]) return -1;
else if (target == nums[l]) return l;
// 在后半段查找目标值
l = rever;
r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
// 返回目标值的索引,如果未找到则返回-1
if (target == nums[l]) return l;
else return -1;
}
}
已知一个长度为 n
的数组,预先按照升序排列,经由 1
到 n
次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7]
在变化后可能得到:
4
次,则可以得到 [4,5,6,7,0,1,2]
7
次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
给你一个元素值 互不相同 的数组 nums
,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入: nums = [3,4,5,1,2]
输出: 1
解释: 原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
if(nums[r] >= nums[l]) return nums[l];
while(l < r) {
int mid = l + r>> 1;
if(nums[mid] > nums[r]) l = mid + 1;
else r = mid;
}
return nums[l];
}
}
给定两个大小分别为 m
和 n
的正序(从小到大)数组 nums1
和 nums2
。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n))
。
示例 1:
输入: nums1 = [1,3], nums2 = [2]
输出: 2.00000
解释: 合并数组 = [1,2,3] ,中位数 2
解法一比较简洁的迭代去二分搜索,每一次去掉K/2个元素
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
// 把求中位数转换成求第k小的数了
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
public int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if(len1 > len2) return getKth(nums2, start2, end2, nums1,start1,end1,k);
if(len1 == 0) return nums2[start2 + k - 1];
if(k == 1) return Math.min(nums1[start1], nums2[start2]);
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if(nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j -start2 + 1));
} else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i -start1 + 1));
}
}
}
解法二:代码有点冗余,但易于理解。解法一二思路都是一样的
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 确保 nums1 的长度小于等于 nums2 的长度
if (m > n) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmp = m;
m = n;
n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
// 寻找正确的划分点,确保左侧元素小于右侧元素
if (i < iMax && nums2[j - 1] > nums1[i]) {
// i 太小,需要增大
iMin = i + 1;
} else if (i > iMin && nums1[i - 1] > nums2[j]) {
// i 太大,需要减小
iMax = i - 1;
} else {
// 找到正确的划分点
// 计算左侧划分的最大值
int maxLeft = 0;
if (i == 0) {
maxLeft = nums2[j - 1];
} else if (j == 0) {
maxLeft = nums1[i - 1];
} else {
maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
}
// 如果总长度为奇数,返回左侧最大值作为中位数
if ((m + n) % 2 == 1) {
return maxLeft;
}
// 计算右侧划分的最小值
int minRight = 0;
if (i == m) {
minRight = nums2[j];
} else if (j == n) {
minRight = nums1[i];
} else {
minRight = Math.min(nums1[i], nums2[j]);
}
// 如果总长度为偶数,返回左侧最大值和右侧最小值的平均值作为中位数
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}