每日一练：LeeCode-35、搜索插入位置【数组】、面试题01.08.零矩阵【数组】、面试题01.07.旋转矩

搜索插入位置、零矩阵、旋转矩阵 每日一练：LeeCode-35、搜索插入位置【数组】方法一（自己写的）方法二二分法 每日一练：面试题 01.08. 零矩阵【数组】每日一练：面试题 01.07. 旋转矩阵【数组+行列翻转】

每日一练：LeeCode-35、搜索插入位置【数组】

LeeCode-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 <= 10^4-10^4 <= nums[i] <= 10^4nums 为 无重复元素 的 升序 排列数组-10^4 <= target <= 10^4 方法一（自己写的） class Solution { public int searchInsert(int[] nums, int target) { int m=0; //记录是否有相等元素的情况 //先遍历一遍数组，判断是否有相等的元素，有则返回索引 for(int i=0;i<nums.length;i++){ if(nums[i]==target){ m=i; return m; } } if(m==0){ //target小于nums数组中除最后一个元素之外的元素 for(int j=0;j<nums.length;j++){ if(nums[j]>target){ m=j;//不能解决大于nums[nums.length-1]的情况 return m; } } //target大于所有数组元素 if(target>nums[nums.length-1]){ m=nums.length; return m; } } return m; } } 方法二 class Solution { public int searchInsert(int[] nums, int target) { for(int i=0;i<nums.length;i++){ if(nums[i]>=target){return i;}//大于的情况，原本nums[i]的值往后移，所以返回的就是新元素插入的位置 } return nums.length;//target大于任何数，所以新加一个位置，放在最后 } } 二分法 class Solution { public int searchInsert(int[] nums, int target) { // 二分法 int left = 0, right = nums.length - 1; while(left <= right){ // 防止 left+right 整型溢出 int mid = left + (right - left) / 2; if(nums[mid] == target){ return mid; }else if(nums[mid] < target){ left = mid + 1; }else if(nums[mid] > target){ right = mid - 1; } } return left;//如果target找不到，left会一直计算到最接近nums[i]其中一个值附近且找到大于它的下一个位置，所以此时就可以把left作为位置返回了 } } 每日一练：面试题 01.08. 零矩阵【数组】

面试题 01.08. 零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

思路： 1.获取原数组的行列数 2.新建新数组来保存原数组 3.遍历找到原数组中元素为0的地方，在新数组中，将对应元素的行列设置为0 4.将新数组替换原数组

class Solution { public void setZeroes(int[][] matrix) { //1.获取原数组的行列数 int rowRecord =matrix.length; int colRecord = matrix[0].length; int maxId1 = rowRecord-1; int maxId2 =colRecord-1; int [][] newMatrix = new int [rowRecord][colRecord]; //新数组作为临时空间 //2.新建新数组来保存原数组 for(int x=0;x<rowRecord;x++){ for(int y=0;y<colRecord;y++){ newMatrix[x][y] = matrix[x][y]; } } //3.遍历找到原数组中元素为0的地方，在新数组中，将对应元素的行列设置为0 for(int x=0;x<rowRecord;x++){ for(int y=0;y<colRecord;y++){ if(matrix[x][y]==0){ for(int i=0;i<rowRecord;i++){ newMatrix[maxId1-i][y]=0; } for(int j=0;j<colRecord;j++){ newMatrix[x][maxId2-j]=0; } } } } //4.将新数组替换原数组 for(int x=0;x<rowRecord;x++){ for(int y=0;y<colRecord;y++){ matrix[x][y] = newMatrix[x][y]; } } } } 每日一练：面试题 01.07. 旋转矩阵【数组+行列翻转】

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。不占用额外内存空间能否做到？

面试题 01.07. 旋转矩阵

class Solution { public void rotate(int[][] matrix) { //获取原数组的行数 int len = matrix.length; if(len==1){ return ; } //新建NXN矩阵，存放原数组的元素 int [][] newMatrix = new int[len][len]; int maxId = len-1; for(int x=0;x<len;x++){ for(int y=0;y<len;y++){ newMatrix[x][maxId-y] = matrix[y][x];//自己画个矩阵比划一下 } } //旋转排序好的新数组替换原数组 for(int i=0;i<len;i++){ for(int j=0;j<len;j++){ matrix[i][j] = newMatrix[i][j]; } } } }