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

704.二分查找力扣题目链接704. 二分查找 - 力扣LeetCode文档讲解704. 二分查找 | 二分查找 | 有序数组 | 循环不变量 | 代码随想录视频讲解手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode704. 二分查找_哔哩哔哩_bilibili状态完成思路题目中“有序的升序数组”、“O(log n)时间复杂度”摆明使用二分法做此题。第一种写法范围左闭右开即[left ,right)//C#publicclassSolution{publicintSearch(int[]nums,inttarget){//左闭右开intrightnums.Length;intleft0;while(rightleft){intmid(rightleft)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid;}}return-1;}}//cppclassSolution{public:intsearch(vectorintnums,inttarget){intleftindex0;intrightindexnums.size()-1;//左闭右闭的区间while(rightindexleftindex){intmid(rightindexleftindex)/2;if(nums[mid]target){returnmid;}if(nums[mid]target){leftindexmid1;}else{rightindexmid-1;}}return-1;}};第二种写法范围左闭右闭即[left ,right]//C#publicclassSolution{publicintSearch(int[]nums,inttarget){//左闭右开intrightnums.Length-1;intleft0;while(rightleft){intmid(rightleft)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid-1;}}return-1;}}//cppclassSolution{public:intsearch(vectorintnums,inttarget){intleftindex0;intrightindexnums.size();//左闭右闭的区间while(rightindexleftindex){intmid(rightindexleftindex)/2;if(nums[mid]target){returnmid;}if(nums[mid]target){leftindexmid1;}else{rightindexmid;}}return-1;}};注意right的赋值循环终止条件的不同27.移除元素力扣题目链接27. 移除元素 - 力扣LeetCode文档讲解27. 移除元素 | 双指针法 | 原地覆盖 | 代码随想录视频讲解数组中移除元素并不容易 | LeetCode27. 移除元素_哔哩哔哩_bilibili状态完成暴力解法思路看到“原地”、把值等于val的元素移到数组最后设想了用冒泡排序改条件来实现//C#publicclassSolution{publicintRemoveElement(int[]nums,intval){intlnums.Length;inttemp;for(inti0;il-1;i){//要循环l - 1次for(intj0;jl-i-1;j)//等价于这个数大要后移if(nums[j]val){tempnums[j];nums[j]nums[j1];nums[j1]temp;}}intcount0;while(countl){if(nums[count]val){returncount;}count;}returnl;}}分析时间复杂度O(n2),空间复杂度O(1)双指针快慢指针法思路用快指针剔除值等于val的元素在原数组上覆写//C#publicclassSolution{publicintRemoveElement(int[]nums,intval){//双指针法intslowindex0;intfastindex0;intlnums.Length;while(fastindexl){if(nums[fastindex]!val){nums[slowindex]nums[fastindex];}fastindex;}returnslowindex;}}//cppclassSolution{public:intremoveElement(vectorintnums,intval){intslowindex0;intfastindex0;intlnums.size();while(fastindexl){if(nums[fastindex]!val){nums[slowindex]nums[fastindex];}fastindex;}returnslowindex;}};分析时间复杂度O(n),空间复杂度O(1)这一遍写的好顺D977.有序数组的平方力扣题目链接977. 有序数组的平方 - 力扣LeetCode文档讲解977.有序数组的平方 | 双指针 | 有序数组 | 平方排序 | 代码随想录视频讲解双指针法经典题目 | LeetCode977.有序数组的平方_哔哩哔哩_bilibili状态完成思路用双指针从两端向绝对值为0的中间逼近按大小写到新的数组里//C#publicclassSolution{publicint[]SortedSquares(int[]nums){int[]ansnewint[nums.Length];intrightindexnums.Length-1;intleftintdex0;intnowindexnums.Length-1;while(leftintdexrightindex){//以绝对值大小为基准决定逼近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:vectorintsortedSquares(vectorintnums){intleftindex0;intrightindexnums.size()-1;vectorintans(nums.size());intnowindexnums.size()-1;while(nowindex0){if(abs(nums[leftindex])nums[rightindex]){ans[nowindex--]pow(nums[rightindex--],2);}else{ans[nowindex--]pow(nums[leftindex],2);}}returnans;}};分析时间复杂度O(n)空间复杂度O(n)‍