代码随想录第一天|二分法、双指针

Leetcode 704 二分查找

题目链接: 二分查找
自己的思路: 由于是有序数组，所以首先想到使用二分查找，通过取左右两边的中点依次判断与目标值的大小，逐渐缩小判断区间。二分查找的难点在于左右指针的初始点，while中的循环条件以及左右指针的更新规则，因为在二分查找的过程中是在[left,right]或者[left,right)中寻找元素，所以分左闭右开和左闭右闭两种。
左闭右闭
当情况为左闭右闭的时候，左指针毋庸置疑是从0索引开始，因为是右闭区间，右指针可以取到右端点，所以右指针的起始点应该为数组长度-1，而while中更新的规则，因为右指针可以取到右边界，所以可以设置left<=right为循环条件，也就是查找过程中right可以和left相等，而更新规则为：left=middle+1,right=middle-1，因为right可以取到middle，所以我们设置right的每次更新为right=middle-1；
左闭右闭
当情况为左闭右开的时候，左指针毋庸置疑是从0索引开始，因为是右开区间，右指针取不到右端点，所以右指针的起始点应该为数组长度，而while中更新的规则，因为右指针取不到右边界，所以可以设置left<right为循环条件，也就是查找过程中right不可以等于left，而更新规则为：left=middle+1,right=middle，因为right可以取不到middle，所以设置middle为右边开区间的部门；
在刚开始学的时候可以练一下两种写法，但是自己如果平时刷题或者笔试的时候还是以一种为主即可。

正确思路: 二分查找
左闭右闭

代码:

class Solution {public int search(int[] nums, int target) {//初始化左右指针为两个端点int left = 0;int right = nums.length - 1;//左闭右闭，right可以取到右边while(left <= right){//防止数值溢出int middle = left + (right-left)/2;//左半区间没有目标值（包括middle）if (nums[middle]<target) left = middle + 1;//右半区间没有目标值（包括middle）else if (nums[middle]>target) right = middle - 1;//找到目标值else return middle;}//整个数组没有目标值return -1;}
}

左闭右开
代码:

class Solution {public int search(int[] nums, int target) {//初始化左右指针为两个端点int left = 0;int right = nums.length;//左闭右开，right取不到右边while(left < right){//防止数值溢出int middle = left + (right-left)/2;//左半区间没有目标值（包括middle）if (nums[middle]<target) left = middle + 1;//右半区间没有目标值（包括middle） 由于right取不到右边，所以设置right为middleelse if (nums[middle]>target) right = middle;//找到目标值else return middle;}//整个数组没有目标值return -1;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(\log (n))$ $n$为数组的长度
空间复杂度：$\mathcal{O}(1)$

相似题型

Leetcode 35 搜索插入位置

题目链接: 搜索插入位置
自己的思路: 由于是有序数组，所以首先想到使用二分查找，如果找到元素，返回它的索引，如果找不到元素，则找第一个大于target的元素，插在其左边即可。如果在数组中找不到元素的话，那么最终right和left落的位置一定是，left在第一个大于该元素的位置，right在left左边一个位置，所以最终返回left即可
正确思路: 二分查找
左闭右闭

代码:

class Solution {public int searchInsert(int[] nums, int target) {//定义左右两个指针int left = 0;int right = nums.length - 1;//左闭右闭while(left<=right){//取中点，防止溢出int middle = left + (right - left)/2;//右边没有，在左边找if (nums[middle] > target) right = middle - 1;//左边没有，在右边找else if (nums[middle] < target) left = middle + 1;//如果在数组中找到元素，返回索引即可else return middle;}//如果找不到元素即返回第一个大于target的索引return left;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(\log (n))$ $n$表示数组的长度
空间复杂度：$\mathcal{O}(1)$

相似题型

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

题目链接: 在排序数组中查找元素的第一个和最后一个位置
自己的思路: 因为题目中要求复杂度是$\mathcal{O}(\log (n))$，而且数组是非递减顺序的数组，所以我们第一个想到的就是二分查找，这里我采用两个二分查找来分别查找target的左边界和右边界，然后让他们两个组成一个数组返回即可。以寻找右边界为例进行讲解，首先和正常的左闭右闭二分法一样的讨论，当nums[middle]<target的时候缩小边界，使left=middle+1，当nums[middle]>target的时候缩小边界，使right=middle-1，不同的点并且最重要的点在于nums[middle]=target的时候，因为要寻找右边界，我们要尽可能地让左指针贴近右指针，也就是贴近右边界，所以我们要动左指针，让左指针left=middle+1，如果动右指针没法保证落在右边界，最后返回的时候要判断数据的有效性，是否不越界并且是否nums[right]的值是否等于target，如果都满足才返回right，否则返回-1。寻找左边界的分析方法同理。
正确思路: 二分查找

代码:

class Solution {public int[] searchRange(int[] nums, int target) {int length = nums.length;if (length==0) return new int[]{-1,-1};int left = searchleft(target,nums,length);int right = searchright(target,nums,length);return new int[]{left,right};}//寻找target的右边界public int searchright(int target,int[] nums,int length){//左右指针int left = 0;int right = length - 1;while(left<=right){//中点，防止溢出int middle = (right-left)/2 + left;//前面两个和二分查找类似if (nums[middle]<target){left = middle + 1;}else if (nums[middle]>target){right = middle - 1;}else{  //注意这里，因为要找的是右边界，所以我们要尽可能地让left向right的位置靠近，所以这里动的//是left，而不是right，如果动right的话不能保证是右边界left = middle + 1;}}//如果right合法返回right，为什么要返回right，因为跳出循环的时候，//nums[right]=target，但是left在right的右边，不能满足nums[left]=targetreturn (right<0||nums[right]!=target)?-1:right;}//寻找target的左边界//和上面寻找右边界同理public int searchleft(int target,int[] nums,int length){int left = 0;int right = length - 1;while(left<=right){int middle = (right-left)/2 + left;if (nums[middle]<target){left = middle + 1;}else if (nums[middle]>target){right = middle - 1;}else{right = middle - 1;}}return (left>length-1||nums[left]!=target)?-1:left;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(\log (n))$ $n$表示数组的长度
空间复杂度：$\mathcal{O}(1)$

相似题型

Leetcode 69 x 的平方根

题目链接: x 的平方根
自己的思路: 比较经典的二分查找，注意要把middle*middle转换成long避免溢出即可。
正确思路: 二分查找

代码:

class Solution {public int mySqrt(int x) {//定义初始左右边界int left = 0;int right = x;//开始二分查找while(left<=right){//中点int middle = (right-left)/2 + left;if ((long)middle*middle<x){left = middle + 1;}else if ((long)middle*middle>x){right = middle - 1;}else{return middle;}}//因为最后跳出循环的时候left一定是大于right的，根据题目信息应该返回较小的那个return right;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(\log (n))$
空间复杂度：$\mathcal{O}(1)$

相似题型

Leetcode 367 有效的完全平方数

题目链接: 有效的完全平方数
自己的思路: 比较经典的二分查找，注意要把middle*middle转换成long避免溢出即可。
正确思路: 二分查找

代码:

class Solution {public boolean isPerfectSquare(int num) {int left = 0;int right = num;while(left<=right){int middle = (right-left)/2 + left;if ((long)middle*middle<num){left = middle + 1;}else if ((long)middle*middle>num){right = middle - 1;}else{return true;}}return false;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(\log (n))$
空间复杂度：$\mathcal{O}(1)$

Leetcode 27 移除元素

题目链接: 移除元素

自己的思路:双指针经典问题，可以定义一个快指针，一个慢指针，快指针在前面判断数组中的值是否等于val，如果不等于则把快指针的值赋给慢指针的位置，然后快慢指针都向前进一步；如果等于，快指针往前进一步，慢指针不动，这样前slow个元素就是移除val以后的数组了，也就是我们想要的。
正确思路:双指针

双指针解法
代码:

class Solution {public int removeElement(int[] nums, int val) {//定义慢指针int slow = 0;//快指针遍历，无论fast处的值等不等于val，快指针都前进一步for (int fast=0;fast<nums.length;fast++){//快指针的值如果不等于val，则将此处的值赋给慢指针位置，慢指针前进一步if (nums[fast]!=val){nums[slow] = nums[fast];slow++;}}//因为最后慢指针++了，所以返回前slow个元素即可return slow;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(1)$

相似题型

Leetcode 26 删除有序数组中的重复项

题目链接: 26

自己的思路:双指针经典问题，可以定义一个快指针，一个慢指针，快指针在前面判断数组中的值是否等于之前慢指针的值，如果不等于则把快指针的值赋给慢指针的位置，然后快慢指针都向前进一步；如果等于，快指针往前进一步，慢指针不动，这样前slow个元素就是移除val以后的数组了，也就是我们想要的。
正确思路:双指针

双指针解法
代码:

class Solution {public int removeDuplicates(int[] nums) {//定义慢指针，由于要判断慢指针前面一个位置的值作为临时变量，所以慢指针必须从1开始int slow = 1;//快指针也必须从1开始，无论如何快指针都前进一步for (int fast=1;fast<nums.length;fast++){//定义临时变量用来记录慢指针前面一个位置的值int temp = nums[slow-1];//如果快指针不等于之前慢指针的值，则把快指针的值赋给慢指针的位置，慢指针前进一步if (nums[fast]!=temp){nums[slow] = nums[fast];slow++;}}//由于最后slow++，所以直接返回slow即可，slow即为新数组的长度return slow;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(1)$

相似题型

Leetcode 283 移动零

题目链接: 移动零

自己的思路:双指针经典问题，可以定义一个快指针，一个慢指针，快指针在前面判断数组中的值是否0，如果值不为0，则交换两个指针的值，如果为0，快指针前进，这样可以把不为0的值都移到前面去，为0的值都移到后面去。
正确思路:双指针

双指针解法
代码:

class Solution {public void moveZeroes(int[] nums) {//定义两个指针int slow = 0;int fast = 0;while(fast<nums.length){//如果快指针的值不为0，就交换两个指针的值if (nums[fast]!=0){int temp = nums[slow];nums[slow] = nums[fast];nums[fast] = temp;slow++;fast++;}else{fast++;}}}
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(1)$

相似题型

Leetcode 844 比较含退格的字符串

题目链接: 比较含退格的字符串

自己的思路:因为’#‘可以去掉前面一个元素，所以我们可以选择使用两个指针i和j从后向前遍历两个字符串，并且定义两个变量sskip和tskip记录两个字符串里面’#‘的个数。以字符串s为例，当当前元素为’#‘时，那么sskip++，i–；当当前元素不为’#'且sskip大于0，那么sskip++，i–；否则直接跳出，然后判断当前的元素和t当前的元素是否相等，如果不相等，返回false，否则继续判断。
正确思路:双指针

双指针解法
代码:

class Solution {public boolean backspaceCompare(String s, String t) {//定义两个指针在两个字符串后面，从后向前遍历int i = s.length()-1;int j = t.length()-1;//记录'#'的个数int sskip = 0;int tskip = 0;//遍历两个字符串while(i>=0||j>=0){//遍历字符串swhile(i>=0){//如果字符串为'#',则'#'个数+1,i--if (s.charAt(i)=='#'){sskip++;i--;//如果字符串不为'#',而且后面的'#'的个数还存在，那么就给它--，i--}else if (sskip>0){sskip--;i--;//如果字符串不为'#',而且sskip为0，直接跳出循环，后面类似}else{break;}}while(j>=0){if (t.charAt(j)=='#'){tskip++;j--;}else if (tskip>0){tskip--;j--;}else{break;}}//当i和j是都是合理索引的时候，判断两个字符串当前值if (i>=0&&j>=0){if (s.charAt(i)!=t.charAt(j)){return false;}}else{     //如果两个里面至少有一个不是合理索引，如果其中一个i是合理索引，直接返回falseif (i>=0||j>=0){return false;}}i--;j--;}//遍历完成，如果没有返回false，即为truereturn true;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(1)$
空间复杂度：$\mathcal{O}(1)$