二分查找(时间复杂度O(logn))1.一个数组(顺序表)2.有序数组3.没有重复元素?1.左闭右闭写法[l,r]int search(vectorint nums, int target) { int n nums.size(); int l 0, r n - 1; sort(nums.begin(), nums.end()); while (l r) { int mid (l r) / 2;//为了防止溢出可以改为int midl(r-l)/2; if (nums[mid] target) { r mid - 1; } else if (nums[mid] target) { l mid 1; } else { return mid; } } return -1; }注意到int mid(lr)/2;可能会导致溢出故修改为int midl(r-l)/2;由于是左闭右闭所以允许lr,同时不论nums[mid]大于还是小于target都已明确说明mid不在需要查找的集合范围里了故rmid-1lmid12.左闭右开写法[l,r)int search(vectorint nums, int target) { int n nums.size(); int l 0, r n - 1; sort(nums.begin(), nums.end()); while (l r) { int mid (l r) / 2; if (nums[mid] target) { r mid; } else if (nums[mid] target) { l mid 1; } else { return mid; } } return -1; }左闭右开l不能等于r,同时查找的范围是[l,r)貌似在插入问题中常用到双指针题例:27. 移除元素 - 力扣LeetCode给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设nums中不等于val的元素数量为k要通过此题您需要执行以下操作更改nums数组使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。返回k。示例 1输入nums [3,2,2,3], val 3输出2, nums [2,2,_,_]解释你的函数应该返回 k 2, 并且 nums中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。示例 2输入nums [0,1,2,2,3,0,4,2], val 2输出5, nums [0,1,4,0,3,_,_,_]解释你的函数应该返回 k 5并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。1.暴力算法(顺序表覆盖)class Solution { public: int removeElement(vectorint nums, int val) { int nnums.size(); for(int i0;in;i) { if(nums[i]val) { for(int ji1;jn;j) { nums[j-1]nums[j]; } i--; n--; } } return n; } };第一个for循环用来遍历第二个for循环用于从后往前的替换删除val,重点是那个i--,每次删除以后i及其以后的元素都往前移动了一位i--2.暴力算法(冒泡)3.快慢指针class Solution { public: int removeElement(vectorint nums, int val) { int nnums.size(); int slowindex0; for(int fastindex0;fastindexn;fastindex) { if(nums[fastindex]!val) { nums[slowindex]nums[fastindex]; slowindex; } } return slowindex; } };fastindex-从头到尾一个一个遍历寻找组成新数组的元素(不等于val的元素)slowindex-定位新数组的下标找到新元素-把新元素赋值给下标为slowindex的元素并让slowindex指向下一个元素没找到新元素-继续寻找,fastindex1直到遍历完毕题例977. 有序数组的平方 - 力扣LeetCode给你一个按非递减顺序排序的整数数组nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。示例 1输入nums [-4,-1,0,3,10]输出[0,1,9,16,100]解释平方后数组变为 [16,1,0,9,100] 排序后数组变为 [0,1,9,16,100]示例 2输入nums [-7,-3,2,3,11]输出[4,9,9,49,121]1.暴力算法(a[i]a[i]*a[i];sort(a.begin(),a.end();O(nnlogn))2.对撞双指针(O(n))class Solution { public: vectorint sortedSquares(vectorint nums) { int nnums.size()-1; vectorintans(n1); int l0,rn; while(lr) { if(nums[l]*nums[l]nums[r]*nums[r]) { ans[n--]nums[l]*nums[l]; l; }else{ ans[n--]nums[r]*nums[r]; r--; } } return ans; } };由于平方的最大值只可能是从最负或者最正的数字得来故可定义指针l,r分别在数组最左侧(最负)和最右侧(最正)不停比较lr元素平方的大小然后赋值到ans中,不需要sort排序了相比原先-nlogn
代码随想录—day1—二分查找与双指针
二分查找(时间复杂度O(logn))1.一个数组(顺序表)2.有序数组3.没有重复元素?1.左闭右闭写法[l,r]int search(vectorint nums, int target) { int n nums.size(); int l 0, r n - 1; sort(nums.begin(), nums.end()); while (l r) { int mid (l r) / 2;//为了防止溢出可以改为int midl(r-l)/2; if (nums[mid] target) { r mid - 1; } else if (nums[mid] target) { l mid 1; } else { return mid; } } return -1; }注意到int mid(lr)/2;可能会导致溢出故修改为int midl(r-l)/2;由于是左闭右闭所以允许lr,同时不论nums[mid]大于还是小于target都已明确说明mid不在需要查找的集合范围里了故rmid-1lmid12.左闭右开写法[l,r)int search(vectorint nums, int target) { int n nums.size(); int l 0, r n - 1; sort(nums.begin(), nums.end()); while (l r) { int mid (l r) / 2; if (nums[mid] target) { r mid; } else if (nums[mid] target) { l mid 1; } else { return mid; } } return -1; }左闭右开l不能等于r,同时查找的范围是[l,r)貌似在插入问题中常用到双指针题例:27. 移除元素 - 力扣LeetCode给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设nums中不等于val的元素数量为k要通过此题您需要执行以下操作更改nums数组使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。返回k。示例 1输入nums [3,2,2,3], val 3输出2, nums [2,2,_,_]解释你的函数应该返回 k 2, 并且 nums中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。示例 2输入nums [0,1,2,2,3,0,4,2], val 2输出5, nums [0,1,4,0,3,_,_,_]解释你的函数应该返回 k 5并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。1.暴力算法(顺序表覆盖)class Solution { public: int removeElement(vectorint nums, int val) { int nnums.size(); for(int i0;in;i) { if(nums[i]val) { for(int ji1;jn;j) { nums[j-1]nums[j]; } i--; n--; } } return n; } };第一个for循环用来遍历第二个for循环用于从后往前的替换删除val,重点是那个i--,每次删除以后i及其以后的元素都往前移动了一位i--2.暴力算法(冒泡)3.快慢指针class Solution { public: int removeElement(vectorint nums, int val) { int nnums.size(); int slowindex0; for(int fastindex0;fastindexn;fastindex) { if(nums[fastindex]!val) { nums[slowindex]nums[fastindex]; slowindex; } } return slowindex; } };fastindex-从头到尾一个一个遍历寻找组成新数组的元素(不等于val的元素)slowindex-定位新数组的下标找到新元素-把新元素赋值给下标为slowindex的元素并让slowindex指向下一个元素没找到新元素-继续寻找,fastindex1直到遍历完毕题例977. 有序数组的平方 - 力扣LeetCode给你一个按非递减顺序排序的整数数组nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。示例 1输入nums [-4,-1,0,3,10]输出[0,1,9,16,100]解释平方后数组变为 [16,1,0,9,100] 排序后数组变为 [0,1,9,16,100]示例 2输入nums [-7,-3,2,3,11]输出[4,9,9,49,121]1.暴力算法(a[i]a[i]*a[i];sort(a.begin(),a.end();O(nnlogn))2.对撞双指针(O(n))class Solution { public: vectorint sortedSquares(vectorint nums) { int nnums.size()-1; vectorintans(n1); int l0,rn; while(lr) { if(nums[l]*nums[l]nums[r]*nums[r]) { ans[n--]nums[l]*nums[l]; l; }else{ ans[n--]nums[r]*nums[r]; r--; } } return ans; } };由于平方的最大值只可能是从最负或者最正的数字得来故可定义指针l,r分别在数组最左侧(最负)和最右侧(最正)不停比较lr元素平方的大小然后赋值到ans中,不需要sort排序了相比原先-nlogn
