35 搜索插入位置

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] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

思路

一般使用二分查找算法需要满足以下两个条件

• 用于查找的内容有序
• 查找的数量只能是一个，而不是多个

举个例子，在一个有序且无重复元素的数组中，例如nums=[1,3,4,8,15,16,18,28]中查找元素16，这样就可以使用二分查找。

二分查找中，目标元素的查找区间定义十分重要。我们要确定查找的范围。主要有以下两种方式

• [left,right] 左闭右闭 （此时while循环为while(left<=right) ）
• [left,right) 左闭右开（此时while循环为while(left<right)）
• 这两种方式的实现会在while循环的判断，以及对right的更新上存在一定的区别。在下面会进行详细说明。

用二分查找，查找区间为[left,right] 左闭右闭的操作查找步骤如下：

nums=[1,3,4,8,15,16,18,28]

下标 = 0,1,2,3,4, 5 , 6, 7

1. l = 0, r = nums.length -1 = 7

2. mid = (l+r)/2 = 3

3. 比较nums[mid] = 8和target = 16 的大小

   1. nums[mid]>target

      说明[mid,right]区间内的所有元素都大于target,此时要去[left,mid-1]区间中查找，更新右边界right

      right = mid -1;

   2. nums[mid]<target （8<16,说明要在[mid+1,right]中找）

      说明[left,mid]区间内的所有元素都小于target,此时要去[mid+1,right]区间中查找,更新左边界left

      left = mid + 1

   3. nums[mid]==target ,直接return mid

不断循环1，2，3直到找到为止，若循环完都没有return说明查找元素在数组中不存在

代码(左闭右闭)

class Solution {public int searchInsert(int[] nums, int target) {/**二分查找，查找区间写为[left,right]*/int l = 0,r = nums.length-1;while(l <= r){int mid = l + (r-l)/2;if(nums[mid]>target){ //注意这里，是将r 更新为mid - 1r = mid-1;}else if(nums[mid]<target){l = mid +1;}else if(nums[mid]==target){return mid;}}return l;}
}

代码(左闭右开)

class Solution {public int searchInsert(int[] nums, int target) {/**二分查找，查找区间写为[left,right]*/int l = 0,r = nums.length; //这里r是nums.length,因为查找范围不包括nums[r]while(l < r){ //这里是l<r,因为查找范围为[l,r)int mid = l + (r-l)/2;if(nums[mid]>target){r = mid; //这里r  = mid,因为查找范围不包括r}else if(nums[mid]<target){l = mid +1;}else if(nums[mid]==target){return mid;}}return l;}
}

74 搜索二维矩阵

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

思路

挺简单的，遍历每一行，获取每一行的第一个元素和最后一个元素，判断target是否在该行中。若在该行中，则使用二分查找，若不在，则继续遍历下一行。

代码(左闭右闭)

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;for(int i = 0;i<m;i++){if(target>=matrix[i][0] && target <=matrix[i][n-1]){int l = 0,r = n-1;while(l<=r){int mid = l + (r-l)/2;if(matrix[i][mid]>target){r = mid -1;}else if(matrix[i][mid]<target){l = mid + 1;}else if(matrix[i][mid]==target){return true;}}}}return false;}
}

34 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

思路

二分查找的变体。

本题中会存在重复的元素，所以需要用二分查找来找到某个元素在数组中第一次出现的位置。将二分查找算法写成函数lowerBound，该函数会找到target第一次出现的位置。调用两次该方法，第一次查找target，第二次查找target+1，这样就能成功返回目标在数组中的开始位置和结束位置。

我们需要考虑边界情况。如果数组为空，或者所有数都<target,那么会返回nums.length，因此lowerBound返回值为nums.length时，直接返回-1，-1，此外还需要判断lowerBound返回的下标在数组中对应的值是否等于target。

lowerBound如何实现呢，和二分查找的差别在于更新右边界，不管nums[mid] <target还是nums[mid]=target , 都会一直往左找，直到找到该元素第一次出现的位置。

if(numd[mid]<target){
l = mid + 1;
}else{
r = mid - 1; //这里不管nums[mid] <target还是nums[mid]=target , 都会一直往左找，直到找到第一个
}

代码

class Solution {public int[] searchRange(int[] nums, int target) {int start = lowerBound(nums,target);if(start == nums.length || nums[start] !=target){return new int[]{-1,-1};}int end = lowerBound(nums,target+1)-1;return new int[]{start,end};}/**lowerBound返回 [最小的]满足nums[i]>=target的i ，如何实现呢也可以理解为找到target第一次出现的位置。如果数组为空，或者所有数都<target,那么会返回nums.lengthif(numd[mid]<target){l = mid + 1;}else{r = mid - 1; //这里不管nums[mid] <target还是nums[mid]=target , 都会一直往左找，直到找到第一个}*/public int lowerBound(int[] nums,int target){int l = 0,r = nums.length-1;while(l<=r){int mid = l + (r-l)/2;if(nums[mid]>target){r = mid - 1;}else if(nums[mid]<target){l = mid + 1;}else if(nums[mid]==target){r = mid - 1;}}return l;}
}

33 搜索旋转排序数组

33. 搜索旋转排序数组

整数数组 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

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

思路

题目分析

本题是在一个可能经过旋转的有序数组中查找给定目标值的问题。由于数组经过旋转，所以它被分为了两个部分，一部分是有序的，另一部分是无序的。我们需要利用这个特点来进行高效的查找。

二分查找，每次查找一定能有一部分是有序的，一部分是无序的
判断target在哪部分，若在有序的部分则直接二分查找，若在无序的部分就继续切割为有序和无序

解题思路

1. 初始化指针
   • 首先，定义两个指针 l 和 r，分别指向数组的首尾位置，表示当前搜索的区间。
2. 循环查找
   • 进入一个循环，只要 l 不超过 r，就继续查找。
   • 在每次循环中，计算当前区间的中间位置 mid，即 mid = l + (r - l)/2。
3. 情况判断
   • 如果 nums[mid] 等于目标值 target，说明找到了目标，直接返回 mid。
   • 如果 nums[mid] 不等于目标值，需要判断当前的中间位置处于哪个区间（有序区间还是无序区间）。
   • 如果nums[l] <= nums[mid]，说明左边[l, mid]是有序区间：
     • 如果目标值 target 在这个有序区间内（即 nums[l] <= target && nums[mid] >= target），那么更新 r 为 mid - 1，继续在有序区间中查找。
     • 如果目标值不在这个有序区间内，说明在无序区间中，此时更新 l 为 mid + 1。
   • 如果nums[mid] <= nums[r]，说明右边[mid, r]是有序区间：
     • 如果目标值 target 在这个有序区间内（即 nums[mid] <= target && nums[r] >= target），那么更新 l 为 mid + 1，继续在有序区间中查找。
     • 如果目标值不在这个有序区间内，说明在无序区间中，此时更新 r 为 mid - 1。
4. 返回结果
   • 如果循环结束后还没有找到目标值，说明目标值不在数组中，返回 -1。

三、算法复杂度分析

1. 时间复杂度：
   • 由于每次循环都将搜索区间缩小一半，所以时间复杂度为O(logn) ，其中 n 是数组的长度。
2. 空间复杂度：
   • 算法只使用了几个额外的变量，不随输入规模增长而增长，所以空间复杂度为O(1) 。

代码

class Solution {public int search(int[] nums, int target) {/**二分查找，每次查找一定能有一部分是有序的，一部分是无序的判断target在哪部分，若在有序的部分则直接二分查找，若在无序的部分就继续切割为有序和无序*/int l = 0,r = nums.length-1;while(l<=r){int mid = l + (r-l)/2;//1.如果当前数等于target，直接返回if(nums[mid]==target){return mid;}else if(nums[l]<=nums[mid]){//2.左边[l,mid]是顺序区间//2.1判断当前元素是否在顺序区间中,若在顺序区间中，更新r为mid-1，继续在顺序区间中查找if(nums[l]<= target && nums[mid]>=target){r = mid - 1;}else{  //不在顺序区间中，在无序区间中l = mid + 1;}}else if(nums[mid]<=nums[r]){//3.右边[mid,r]是顺序区间//3.1 判断当前元素是否在顺序区间中//3.2 若在顺序区间中，更新l 为mid + 1,继续在顺序区间[l,r]中查找if(nums[mid]<=target && nums[r]>=target){l = mid + 1;}else{r = mid - 1; //在无需区间中查找}}}return -1;}
}

153 寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值

已知一个长度为 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 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

思路

实现思路

1. 利用二分查找的思想，通过比较中间元素和数组末尾元素的大小关系来确定最小值所在的区间，不断缩小区间范围，直到找到最小值。
2. 由于数组经过旋转后被分为了两个部分，一部分是原升序数组的某个子区间，另一部分是旋转后的子区间，最小值就在这两个区间的交界处。通过比较中间元素和末尾元素，可以确定当前中间元素处于哪个子区间，从而缩小查找范围。

具体实现步骤

1. 初始化指针
   • 定义两个指针 l 和 r，分别指向数组的首和尾位置，表示当前搜索的区间范围。初始时，l = 0，r = nums.length - 1。
2. 进入循环
   • 进入一个循环，只要 l 小于等于 r，就继续查找。
3. 计算中间位置
   • 在每次循环中，计算当前区间的中间位置 mid，即 mid = l + (r - l)/2。
4. 情况判断与区间调整
   • 如果nums[mid] <= nums[n - 1]：
     • 说明 [mid, r] 为翻转后的递增区间，此时最小值一定在 [l, mid - 1] 中，所以将 r 更新为 mid - 1。
   • 如果nums[mid] > nums[n - 1]：
     • 说明 [l, mid] 为未翻转的递增区间，那最小值一定在 [mid + 1, r] 中，所以将 l 更新为 mid + 1。
   • 如果nums[mid] == nums[n - 1]：
     • 说明无法确定最小值在哪个区间，但因为最终要返回 l，所以将 r 更新为 mid - 1，缩小搜索范围。
5. 返回结果
   • 循环结束后，l 指向的位置就是数组中的最小值，返回 nums[l]。

算法复杂度分析

1. 时间复杂度：
   • 由于每次循环都将搜索区间缩小一半，所以时间复杂度为 O(logn)，其中 n 是数组的长度。
2. 空间复杂度：
   • 算法只使用了几个额外的变量，不随输入规模增长而增长，所以空间复杂度为 O(1)。

代码

class Solution {public int findMin(int[] nums) {/**[4,5,6,7,0,1,2]使用nums[mid]和nums[n-1]比不停的拿中间的数和最后一个数比较，缩小区间，一共有三种情况nums[mid]<nums[n-1] : 说明[mid,r]为翻转后的递增区间,此时最小值一定在[l,mid-1]中nums[mid]>nums[n-1]: 说明[l,mid]为未翻转的递增区间，那最小值一定在[mid+1,r]中nums[mid]==nums[n-1]:说明最小值为n-1,因为我们要返回l,所以将r更新为mid-1不断缩小区间，最终找到最小值返回*/int l = 0,r = nums.length-1;int n = nums.length;while(l <= r){int mid = l + (r-l)/2;if(nums[mid]<=nums[n-1]){ //r = mid - 1;}else {l = mid + 1;}}return nums[l];}
}

4 寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

思路

解题思路

1. 将求两个有序数组的中位数问题转化为求两个数组合并后第k小的数的问题。
2. 利用二分查找的思想，每次排除一定数量的元素，逐步缩小搜索范围，直到找到第k小的数。

边界情况考虑

1. 当其中一个数组到达边界时：
   • 如果已经到达数组nums1的边界，此时要求的第k小的元素即为nums2开始的第k个，直接返回nums2[index2 + k - 1]。
   • 同理，如果已经到达数组nums2的边界，返回nums1[index1 + k - 1]。
2. 当k = 1时：
   • 需要找到两个数组中第 1 小的数，直接返回两个数组开头的最小值。

具体实现步骤

1. 求中位数的主方法
   • 首先，计算两个数组的长度m和n。
   • 如果合并后的数组大小为奇数，直接求第(m + n)/2 + 1小的数即可，将结果强制转换为double类型后返回。
   • 如果合并后的数组大小为偶数，那么需要求解第(m + n)/2和第(m + n)/2 + 1小的数，然后取平均并返回。
2. 求第k小的数的辅助方法
   • 初始化两个数组的指针index1和index2，分别指向nums1和nums2的起始位置。
   • 进入一个循环，在循环中不断缩小搜索范围，直到找到第k小的数。
   • 在每次循环中，首先判断边界情况：
     • 如果到达nums1的边界，返回nums2[index2 + k - 1]。
     • 如果到达nums2的边界，返回nums1[index1 + k - 1]。
     • 如果k = 1，返回两个数组开头的较小值。
   • 正常处理时，为了后续比较的方便，先求出A[k/2 - 1]和B[k/2 - 1]的下标，但要注意不能直接index + k/2 - 1，可能会越界，应该使用Math.min(index + k/2, array.length) - 1来计算。
   • 判断nums1[newIndex1]和nums2[newIndex2]的大小：
     • 如果nums1[newIndex1] > nums2[newIndex2]，说明可以排除掉nums2中[index2,...,index2 + k/2 - 1]的部分，更新index2 = index2 + k/2，同时更新k的值为k -= newIndex2 - index2 + 1。
     • 如果nums1[newIndex1] < nums2[newIndex2]，可以排除掉nums1中[index1,...,index1 + k/2 - 1]的部分，更新index1 = index1 + k/2，更新k的值为k -= newIndex1 - index1 + 1。

五、算法复杂度分析

1. 时间复杂度：
   • 由于每次循环都将搜索范围缩小一半，所以时间复杂度为O(logn)，其中m和n分别是两个数组的长度。
2. 空间复杂度：
   • 算法只使用了几个额外的变量，不随输入规模增长而增长，所以空间复杂度为O(1)。

代码

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {/**使用求两个数组中第k小的数来求解中位数。两种情况1.合并后的数组大小为奇数num，则直接求第 num/2+1 小的数即可2.合并后的数组大小为偶数num，那么需要求解第 num/2 ，和第num/2+1小的数，然后再取平均*/int m = nums1.length,n = nums2.length;if((m+n)%2!=0){int mid = getKthElement(nums1,nums2,(m+n)/2+1);return (double)mid;}else{double mid1 = getKthElement(nums1,nums2,(m+n)/2);double mid2 = getKthElement(nums1,nums2,(m+n)/2+1);return (mid1+mid2)/2;}}/**转换为求两个数组中第k小的数，因为时间复杂度需要为O(log(m+n)),因此考虑二分查找的办法。每次排除都排除k/2个元素。假设有A,B两个数组，现在要求A,B数组合并后的第k小的数求A[k/2-1] B[k/2-1]的值，判断这两个的大小1.若A[K/2-1] > B[k/2-1]，说明B[0,...,k/2-1]中的k/2个数一定不会是第k小的数，所以更新B的下标，排除B[0,...,k/2-1]2.反之若A[k/2-1] < B[k/2-1] 说明A[0,...,k/2-1]中的k/2个数一定不会是第k小的数，所以更新A的下标，排除A[0,...,k/2-1]相等的话，排除A和B都行，这里排除A在排除A/B的k/2个元素后，我们现在需要在新的数组中找到第k - k/2 小的元素，因此更新k = k-k/2注意边界条件：1.假如已经到达A/B数组的边界，以A为例，已经到达数组A的边界此时要求的第k小的元素即为B开始的第k个，直接返回B[index + k - 1],反之则返回A[index+k-1]2.假如k=1，需要找到两个数组中第1小的数，直接返回两个数组开头的最小值*/private int getKthElement(int nums1[],int nums2[],int k){int index1 = 0,index2 = 0;while(true){//1.判断边界条件//1.1 到达数组1的边界,返回数组2中第k小的数if(index1==nums1.length){return nums2[index2+k-1];}//1.2 到达数组2的边界，返回数组1中第k小的数if(index2==nums2.length){return nums1[index1+k-1];}//1.3 k==1，需要找到两个数组中第1小的数,直接取两个数组中index较小的数if(k==1){return Math.min(nums1[index1],nums2[index2]);}//2.正常处理// 2.1 为了后续比较的方便，先求出A[k/2-1]和B[k/2-1]的下标// newIndex1 等价于 A的k/2-newIndex2 等价于B的k/2-1// 注意，直接index+k/2-1会越界！！！，所以不能这样。// int newIndex1 = index1 + k/2 - 1;// int newIndex1 = index2 + k/2 -1;int newIndex1 = Math.min(index1+k/2,nums1.length)-1;int newIndex2 = Math.min(index2+k/2,nums2.length)-1;//2.2 判断A[k/2-1]和B[k/2-1]的大小，即判断A[pivot1]和B[pivot2]的大小//2.2.1 nums1[k/2-1] > nums2[index2 + k/2-1],可以排除掉nums2中[index2,...,index2+k/2-1]的部分，更新index2 = index2 + k/2,同时更新k的值if(nums1[newIndex1]>nums2[newIndex2]){//（1）更新k的值k -= newIndex2-index2+1;//（2）排除掉后，更新index2的值index2 = newIndex2+1;}else {//2.2.2 nums1[k/2-1] < nums2[index2 + k/2-1],可以排除掉nums1中[index1,...,index1+k/2-1]的部分，更新index1 = index1 + k/2// 注意这里等于的情况放在哪里都可以。//（1）更新k的值k -= newIndex1 - index1 +1;//（2）排除掉后，更新index1的值index1 = newIndex1 +1;}// （×）2.2.3 更新k，因为已经排除掉了k/2个元素，现在只需要求k-k/2小的值,// k = k - k/2;}}
}