怎么用阿里云建网站,南京营销型网站制作,做类似慕课网的网站要多少钱,公司注册公司代理文章目录 1.搜索插入位置1.答案2.思路 2.搜索二维矩阵1.答案2.思路 3.寻找峰值1.答案2.思路 4.搜索旋转排序数组1.答案2.思路 5.在排序数组中查找元素的第一个和最后一个位置1.答案2.思路 6.寻找旋转排序数组中的最小值1.答案2.思路 1.搜索插入位置
1.答案
package com.sunxi… 文章目录 1.搜索插入位置1.答案2.思路 2.搜索二维矩阵1.答案2.思路 3.寻找峰值1.答案2.思路 4.搜索旋转排序数组1.答案2.思路 5.在排序数组中查找元素的第一个和最后一个位置1.答案2.思路 6.寻找旋转排序数组中的最小值1.答案2.思路 1.搜索插入位置
1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 35. 搜索插入位置** Author sun* Create 2025/1/30 10:11* Version 1.0*/
public class t35 {public static int searchInsert(int[] nums, int target) {// 左闭右闭加等号int left 0, right nums.length - 1;while (left right) {// 求中点int mid left (right - left) / 2;if (nums[mid] target) {return mid;}if (nums[mid] target) {left mid 1;}if (nums[mid] target) {right mid - 1;}}// 如果找不到就返回应该插入的位置return left;}
}2.思路
左闭右闭加等号求中点找不到就返回left
2.搜索二维矩阵
1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 74. 搜索二维矩阵** Author sun* Create 2025/1/30 10:16* Version 1.0*/
public class t74 {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length;int n matrix[0].length;// 左闭右闭int left 0, right m * n - 1;// 加等号while (left right) {// 求中点int mid left (right - left) / 2;// 转换中点下标为二维数组的下标int i mid / n;int j mid % n;if (matrix[i][j] target) {return true;}if (matrix[i][j] target) {left mid 1;}else if (matrix[i][j] target) {right mid - 1;}}return false;}
}2.思路
就是在求中点的时候有些不一样需要将数字转换为二维数组的下标公式就是x / n 和 x % n
3.寻找峰值
1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 162. 寻找峰值** Author sun* Create 2025/1/30 10:35* Version 1.0*/
public class t162 {public int findPeakElement(int[] nums) {// 左闭右闭加等号int left 0, right nums.length - 1;while (left right) {int mid left (right - left) / 2;// 判断是否大于左右边元素boolean leftSmaller mid 0 || nums[mid] nums[mid - 1];boolean rightSmaller (mid nums.length - 1) || nums[mid] nums[mid 1];// 如果都大于则当前元素就是峰值if (leftSmaller rightSmaller) {return mid;}// 如果比左边的元素大则峰值在右边if (leftSmaller) {left mid 1;} else {// 其余情况峰值在左边right mid - 1;}}return -1;}
}2.思路
除了二分老套路之外还要判断是否大于左右边元素如果都大于就是峰值如果只是大于左边但是小于右边那么峰值就在右边
4.搜索旋转排序数组
1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 33. 搜索旋转排序数组** Author sun* Create 2025/1/30 11:05* Version 1.0*/
public class t33 {public static int search(int[] nums, int target) {if (nums null || nums.length 0) {return -1;}// 左闭右闭加等号int left 0, right nums.length - 1;while (left right) {// 求中点int mid left (right - left) / 2;// 找到了就直接返回if (target nums[mid]) {return mid;}// 找不到如果左边是有序的if (nums[mid] nums[left]) {// 判断是否在左边if (target nums[left] target nums[mid]) {right mid - 1;} else {left mid 1;}} else {// 目前是右边有序则判断是否在右边if (target nums[right] target nums[mid]) {left mid 1;} else {right mid - 1;}}}return -1;}
}2.思路
左闭右闭加等号求中点如果找不到就判断左边是不是有序的如果左边有序就进一步判断元素是否在左边如果在就right mid - 1否则就是left mid 1右边也是同理
5.在排序数组中查找元素的第一个和最后一个位置
1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 34. 在排序数组中查找元素的第一个和最后一个位置** Author sun* Create 2025/1/30 11:23* Version 1.0*/
public class t34 {public int[] searchRange(int[] nums, int target) {if (nums null || nums.length 0) {return new int[]{-1, -1};}return new int[]{getFirst(nums, target), getLast(nums, target)};}private int getFirst(int[] nums, int target) {// 左闭右闭加等号int left 0, right nums.length - 1;while (left right) {// 求中点int mid left (right - left) / 2;if (target nums[mid]) {right mid - 1;} else {left mid 1;}}// 防止越界if (left 0 || left nums.length - 1) {return -1;}return nums[left] target ? left : -1;}private int getLast(int[] nums, int target) {// 左闭右闭加等号int left 0, right nums.length - 1;while (left right) {// 求中点int mid left (right - left) / 2;if (target nums[mid]) {left mid 1;} else {right mid - 1;}}// 防止越界if (right 0 || right nums.length - 1) {return -1;}return nums[right] target ? right : -1;}
}2.思路
以找到第一个元素为例首先还是二分老套路然后如果target小于等于mid的元素就在左边否则在右边注意退出循环后要防止越界并且最后返回的时候也要判断left下的元素是不是那个元素
6.寻找旋转排序数组中的最小值
1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 153. 寻找旋转排序数组中的最小值** Author sun* Create 2025/1/30 13:07* Version 1.0*/
public class t153 {public int findMin(int[] nums) {// 左闭右闭加等号int left 0, right nums.length - 1;int res nums[left];while (left right) {// 求中点int mid left (right - left) / 2;// 更新最小值res Math.min(res, nums[mid]);// 将right指向的元素当做targetif (nums[mid] nums[right]) {right mid - 1;} else {left mid 1;}}return res;}
}2.思路
在二分的基础上加了一个更新最小值的操作并且将right指向的元素当做target进行更新左右边界的操作
