当前位置：首页 > news >正文

代码随想录算法训练营第一天 | Leetcode 704.二分查找 | Leetcode 27.移除元素 | Leetcode 977.有序数组的平方 (c#和c++双语)

news 2026/6/11 21:36:19

704.二分查找

力扣题目链接：704. 二分查找 - 力扣（LeetCode）
文档讲解：704. 二分查找 | 二分查找 | 有序数组 | 循环不变量 | 代码随想录
视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili
状态：完成

思路：题目中“有序的升序数组”、“O(log n)时间复杂度”摆明使用二分法做此题。

第一种写法，范围左闭右开即[left ,right)：

//C#publicclassSolution{publicintSearch(int[]nums,inttarget){//左闭右开intright=nums.Length;intleft=0;while(right>left){intmid=(right+left)/2;if(nums[mid]==target){returnmid;}elseif(nums[mid]<target){left=mid+1;}else{right=mid;}}return-1;}}

//cppclassSolution{public:intsearch(vector<int>&nums,inttarget){intleftindex=0;intrightindex=nums.size()-1;//左闭右闭的区间while(rightindex>=leftindex){intmid=(rightindex+leftindex)/2;if(nums[mid]==target){returnmid;}if(nums[mid]<target){leftindex=mid+1;}else{rightindex=mid-1;}}return-1;}};

第二种写法，范围左闭右闭即[left ,right]：

//C#publicclassSolution{publicintSearch(int[]nums,inttarget){//左闭右开intright=nums.Length-1;intleft=0;while(right>=left){intmid=(right+left)/2;if(nums[mid]==target){returnmid;}elseif(nums[mid]<target){left=mid+1;}else{right=mid-1;}}return-1;}}

//cppclassSolution{public:intsearch(vector<int>&nums,inttarget){intleftindex=0;intrightindex=nums.size();//左闭右闭的区间while(rightindex>leftindex){intmid=(rightindex+leftindex)/2;if(nums[mid]==target){returnmid;}if(nums[mid]<target){leftindex=mid+1;}else{rightindex=mid;}}return-1;}};

注意right的赋值，循环终止条件的不同

27.移除元素

力扣题目链接：27. 移除元素 - 力扣（LeetCode）
文档讲解：27. 移除元素 | 双指针法 | 原地覆盖 | 代码随想录
视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili
状态：完成

暴力解法：

思路：看到“原地”、把值等于val的元素移到数组最后，设想了用冒泡排序改条件来实现

//C#publicclassSolution{publicintRemoveElement(int[]nums,intval){intl=nums.Length;inttemp;for(inti=0;i<l-1;i++){//要循环l - 1次for(intj=0;j<l-i-1;j++)//等价于这个数大（要后移）if(nums[j]==val){temp=nums[j];nums[j]=nums[j+1];nums[j+1]=temp;}}intcount=0;while(count<l){if(nums[count]==val){returncount;}count++;}returnl;}}

分析：时间复杂度O(n2),空间复杂度O(1)

双指针（快慢指针）法：

思路：用快指针剔除值等于val的元素，在原数组上覆写

//C#publicclassSolution{publicintRemoveElement(int[]nums,intval){//双指针法intslowindex=0;intfastindex=0;intl=nums.Length;while(fastindex<l){if(nums[fastindex]!=val){nums[slowindex++]=nums[fastindex];}fastindex++;}returnslowindex;}}

//cppclassSolution{public:intremoveElement(vector<int>&nums,intval){intslowindex=0;intfastindex=0;intl=nums.size();while(fastindex<l){if(nums[fastindex]!=val){nums[slowindex++]=nums[fastindex];}fastindex++;}returnslowindex;}};

分析：时间复杂度O(n),空间复杂度O(1)

（这一遍写的好顺=D）

977.有序数组的平方：

力扣题目链接：977. 有序数组的平方 - 力扣（LeetCode）
文档讲解：977.有序数组的平方 | 双指针 | 有序数组 | 平方排序 | 代码随想录
视频讲解：双指针法经典题目 | LeetCode：977.有序数组的平方_哔哩哔哩_bilibili
状态：完成

思路：用双指针从两端向绝对值为0的中间逼近，按大小写到新的数组里

//C#publicclassSolution{publicint[]SortedSquares(int[]nums){int[]ans=newint[nums.Length];intrightindex=nums.Length-1;intleftintdex=0;intnowindex=nums.Length-1;while(leftintdex<=rightindex){//以绝对值大小为基准决定逼近if(Math.Abs(nums[leftintdex])<=nums[rightindex]){ans[nowindex--]=(int)Math.Pow(nums[rightindex--],2);}elseif(Math.Abs(nums[leftintdex])>nums[rightindex]){ans[nowindex--]=(int)Math.Pow(nums[leftintdex++],2);}}returnans;}}

//cppclassSolution{public:vector<int>sortedSquares(vector<int>&nums){intleftindex=0;intrightindex=nums.size()-1;vector<int>ans(nums.size());intnowindex=nums.size()-1;while(nowindex>=0){if(abs(nums[leftindex])<nums[rightindex]){ans[nowindex--]=pow(nums[rightindex--],2);}else{ans[nowindex--]=pow(nums[leftindex++],2);}}returnans;}};