今天的两道题都是有点硬的骨头，勉勉强强能做出来，但是想不到特定的解决方法，算法难度★★★★。深度优先算法和二分查找以为自己会，遇到这两道题算是给了我当头两棒：根本不知道何时用、怎么用深度优先算法，以及想了很久也没理解第二题的二分查找法。被原来的简单题迷得稀里糊涂，遇到困难题就知道世道的险恶了。
一.岛屿的周长 ★★★☆☆
题目
463. 岛屿的周长
给定一个row x col的二维网格地图grid，其中：grid[i][j] = 1表示陆地，grid[i][j] = 0表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长
我的思路
由观察可以看出来，陆地的某一边界时二维网格的边界时，该边一定属于岛屿周长的一部分；同时，其他不是边界的边，如果没有和其他陆地相邻，也是岛屿周长的一部分。由此可以写成双层循环并通过 if 判断语句完成周长的计算。
代码
int islandPerimeter(int** grid, int gridSize, int* gridColSize) { //遍历陆地 //当它处于边界时，周长+1 //当它的周围没有陆地时，周长++ int sum=0; for(int i=0;i<gridSize;i++){ for(int j=0;j<gridColSize[i];j++){ if(grid[i][j]==1){ if(i-1<0 || grid[i-1][j]==0){ sum++; } if(i+1==gridSize || grid[i+1][j]==0){ sum++; } if(j-1<0 || grid[i][j-1]==0){ sum++; } if(j+1==gridColSize[i] || grid[i][j+1]==0){ sum++; } } } } return sum; }复杂度
m、n分别是二维网格的行数和列数
时间复杂度：O(mn)——双层嵌套循环
空间复杂度：O(1)——只有sum变量申请了空间
官方题解
思路1——迭代
我的思路和这一个思路大差不差，只是官方的代码写法不太一样。
利用了方向数组来避免重复的 if 语句：const int dx[4]——控制x方向上的移动；const int dy[4]——控制y方向上的移动，用循环替代重复的方向判断。在遍历每个陆地的时候，在我的代码中通过重复且固定的通过索引的变化获取上下左右四个方位的信息，而这里只需要一个for循环来获取信息。用tx和ty表示新坐标，直接将所有可能的情况写在一个 if 语句中即可实现四个方位点的判断。
代码
const int dx[4]={0,1,0,-1}; const int dy[4]={1,0,-1,0}; int islandPerimeter(int** grid, int gridSize, int* gridColSize) { int n=gridSize,m=gridColSize[0]; int sum=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j]){ for(int k=0;k<4;k++){ int tx=i+dx[k]; int ty=j+dy[k]; if(tx<0||tx>=n||ty<0||ty>=m||!grid[tx][ty]) sum++; } } } } return sum; }复杂度
m、n分别是二维网格的行数和列数
时间复杂度：O(mn) —— 需要遍历每个格子，每个格子要看其周围 4 个格子是否为岛屿，因此总时间复杂度为 O(4nm)=O(nm)
空间复杂度：O(1) —— 只需要常数空间存放若干变量
思路2——深度优先dfs ★★★★☆
将方法一改成深度优先搜索遍历的方式，此时遍历的方式可扩展至统计多个岛屿各自的周长。需要注意的是为了防止陆地格子在深度优先搜索中被重复遍历导致死循环，我们需要将遍历过的陆地格子标记为已经遍历过，下面的代码中我们设定值为 2 的格子为已经遍历过的陆地格子。
代码
const int dx[4]={0,1,0,-1}; const int dy[4]={1,0,-1,0}; int dfs(int x,int y,int**grid,int n,int m){ if(x<0||x>=n||y<0||y>=m||grid[x][y]==0){ return 1; } if(grid[x][y]==2){ return 0; } grid[x][y]=2; int res=0; for(int i=0;i<4;i++){ int tx=i+dx[i]; int ty=j+dy[i]; res+=dfs(tx,ty,grid,n,m); } return res; } int islandPerimeter(int** grid, int gridSize, int* gridColSize) { int n=gridSize,m=gridColSize[0]; int sum=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j]){ sum+=dfs(i,j,grid,n,m); } } } return sum; }复杂度
m、n分别是二维网格的行数和列数
时间复杂度：O(mn)。每个格子至多会被遍历一次，因此总时间复杂度为 O(mn)
空间复杂度：O(mn)。深度优先搜索复杂度取决于递归的栈空间，而栈空间最坏情况下会到 O(nm)
二.寻找两个正序数组中的中位数 ★★☆☆☆
题目
4. 寻找两个正序数组的中位数 给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
这道题做出来不难，要使时间复杂度O(log(m+n))就难了，我也只是做了出来
思路
合并两个数字，通过合并后的数字个数 m+n 的奇偶决定中位数的值：奇数——nums[(m+n)/2]；偶数——(nums[(m+n)/2-1]+nums[(m+n)/2])/2
代码1
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { //1.合并数组 //2.找中位数→数字个数奇/偶 int m=nums1.size(); int n=nums2.size(); double res=0; vector<int> nums(m+n); int i=0,j=0,k=0; while(i<m && j<n){ if(nums1[i]<nums2[j]){ nums[k++]=nums1[i++]; }else{ nums[k++]=nums2[j++]; } } while(i<m) nums[k++]=nums1[i++]; while(j<n) nums[k++]=nums2[j++]; if((m+n) % 2==0){ res=(nums[(m+n)/2-1]+nums[(m+n)/2])*1.0/2; }else{ res=nums[(m+n)/2]; } return res; } };复杂度
时间复杂度：O(m+n)
空间复杂度：O(m+n)
代码2
不合并整个数组，而是直接找到“中间”的数即可。用pre和cur记录前一个数和当前的数，用k表示遍历的数字的个数，当k==(m+n)/2时就停止循环。
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { //1.合并数组 //2.找中位数→数字个数奇/偶 int m=nums1.size(); int n=nums2.size(); double res=0.0; int i=0,j=0,k=0; int pre=0,cur=0; while(i<m && j<n && k<=(m+n)/2){ pre=cur; if(nums1[i]<nums2[j]){ cur=nums1[i++]; }else{ cur=nums2[j++]; } k++; } while(i<m && k<=(m+n)/2){ pre=cur; cur=nums1[i++]; k++; } while(j<n && k<=(m+n)/2){ pre=cur; cur=nums2[j++]; k++; } if((m+n) % 2==0){ res=(cur+pre)*1.0/2; }else{ res=cur; } return res; } };复杂度
时间复杂度：O(m+n)
空间复杂度：O(1)
官方题解
思路1——二分查找 ★★★★☆
好难理解啊（倒）
明天再理解试试。
代码
class Solution { public: int getKthElement(const vector<int>& nums1,vector<int>& nums2,int k){ int m=nums1.size(); int n=nums2.size(); int index1=0,index2=0; while(true){ if(index1==m){ return nums2[index2+k-1]; } if(index2==n){ return nums1[index1+k-1]; } if(k==1){ return min(nums1[index1],nums2[index2]); } int newIndex1=min(index1+k/2-1,m-1); int newIndex2=min(index2+k/2-1,n-1); int pivot1=nums1[newIndex1]; int pivot2=nums2[newIndex2]; if(pivot1<=pivot2){ k-=newIndex1-index1+1; index1=newIndex1+1; } else{ k-=newIndex2-index2+1; index2=newIndex2+1; } } } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int totalLen=nums1.size()+nums2.size(); if(totalLen%2==1){ return getKthElement(nums1,nums2,(totalLen+1)/2); }else{ return (getKthElement(nums1,nums2,(totalLen/2))+getKthElement(nums1,nums2,totalLen/2+1))/2.0; } } };复杂度
时间复杂度：O(log(m+n))，其中 m 和 n 分别是数组 nums 1和 nums 2的长度。初始时有 k=(m+n)/2 或 k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是 O(log(m+n))
空间复杂度：O(1)
思路2——划分数组
代码
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { if (nums1.size() > nums2.size()) { return findMedianSortedArrays(nums2, nums1); } int m = nums1.size(); int n = nums2.size(); int left = 0, right = m; // median1：前一部分的最大值 // median2：后一部分的最小值 int median1 = 0, median2 = 0; while (left <= right) { // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1] // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1] int i = (left + right) / 2; int j = (m + n + 1) / 2 - i; // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j] int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]); int nums_i = (i == m ? INT_MAX : nums1[i]); int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]); int nums_j = (j == n ? INT_MAX : nums2[j]); if (nums_im1 <= nums_j) { median1 = max(nums_im1, nums_jm1); median2 = min(nums_i, nums_j); left = i + 1; } else { right = i - 1; } } return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1; } };复杂度
时间复杂度：O(logmin(m,n)))，其中 m 和 n 分别是数组 nums 1和 nums 2的长度。查找的区间是 [0,m]，而该区间的长度在每次循环之后都会减少为原来的一半。所以，只需要执行 logm 次循环。由于每次循环中的操作次数是常数，所以时间复杂度为 O(logm)。由于我们可能需要交换 nums1和 nums2使得 m≤n，因此时间复杂度是 O(logmin(m,n)))。
空间复杂度：O(1)。
