代码随想录算法训练营第一天|704二分查找+27移除元素+977有序数组的平方（+34. 在排序数组中查找元素的第一个和最后一个位置）

非原创搬运记录解题方法学习思路一同进步Day1备忘704. 二分查找思路代码34. 在排序数组中查找元素的第一个和最后一个位置思路代码27.移除元素思路代码977.有序数组的平方思路代码总结备忘完成三题并搞懂思路将方法融汇贯通完成相关题目0/1704. 二分查找给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果 target 存在返回下标否则返回 -1。你必须编写一个具有 O(log n) 时间复杂度的算法。思路利用红蓝分区法就是第一个大于等于target的值或者是最后一个小于等于target的值。这里用的是第一个大于等于target的值进行求解。代码defsearch(self,nums:List[int],target:int)-int:nlen(nums)i,j-1,len(nums)whilei1!j:midi(j-i)//2ifnums[mid]target:jmidelse:imidifjlen(nums)ornums[j]!target:return-1else:returnj34. 在排序数组中查找元素的第一个和最后一个位置给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。思路利用红蓝分区找到边界左侧为target的第一个即红区第一个为r右侧为target的最后一个即蓝区最后一个为l)参考https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/967331/lan-hong-hua-fen-fa-dan-mo-ban-miao-sha-e7r40代码classSolution:defsearchRange(self,nums:List[int],target:int)-List[int]:defFindLeft(nums,target):l-1rlen(nums)whilel1!r:midl(r-l)//2ifnums[mid]target:rmidelse:lmidreturnrdefFindRight(nums,target):l-1rlen(nums)whilel1!r:midl(r-l)//2ifnums[mid]target:lmidelse:rmidreturnl leftborderFindLeft(nums,target)rightborderFindRight(nums,target)ifleftborderrightborderandrightborderlen(nums)andnums[leftborder]targetandnums[rightborder]target:return[leftborder,rightborder]return[-1,-1]27.移除元素给你一个数组 nums 和一个值 val你需要 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。思路本题考察的是双指针的运用但也可以将它视为栈。栈思路很简单避开指定val将其他数值压入栈中等待循环结束打印栈。栈参考https://leetcode.cn/problems/remove-element/solutions/2802809/jian-dan-ti-jian-dan-zuo-pythonjavaccgoj-72bn双指针就是两个指针各司其职左指针i记录位置右指针(j)找到非val的元素位置将该位置刷新给左指针i后两个指针同时右移继续之前的操作。双指针参考https://leetcode.cn/problems/remove-element/solutions/969722/si-wei-dao-tu-zheng-li-yi-chu-yuan-su-de-egg5代码栈classSolution:defremoveElement(self,nums:List[int],val:int)-int:stack_num0forxinnums:ifx!val:nums[stack_num]x stack_num1returnstack_num双指针classSolution:defremoveElement(self,nums:List[int],val:int)-int:i0nlen(nums)forjinrange(0,n):ifval!nums[j]:nums[i]nums[j]i1returni977.有序数组的平方给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。思路暴力解法先全部平方再全部排序。双指针解法负数平方可能大于某个值所以两边各一个指针平方后进行比较。要求是非递减那么从后往前依次比较。代码暴力解法defsortedSquares(self,nums:List[int])-List[int]:squared[x**2forxinnums]squared.sort()returnsquared双指针解法defsortedSquares(self,nums:List[int])-List[int]:nlen(nums)sorted[0]*n i,j0,n-1forpinrange(n-1,-1,-1):xnums[i]*nums[i]ynums[j]*nums[j]ifxy:sorted[p]x i1else:sorted[p]y j-1returnsorted总结重点学习二分法更深入的学会非一维的情况。