算法训练第一天

704.二分查找

思路：

这道题其实没什么好说的，最经典的二分查找算法应用。个人习惯一直用的都是左闭右闭的方式。

代码：

class Solution:def search(self, nums: List[int], target: int) -> int:left = 0right = len(nums)-1while left<=right:mid = left+right>>1if nums[mid]<target:left = mid+1elif nums[mid]>target:right = mid-1else:return midreturn -1

27.移除元素

思路：

从题目上看需要原地移除所有数值等于 val 的元素，并且从示例2中：输入：nums = [0,1,2,2,3,0,4,2], val = 2，输出：5, nums = [0,1,4,0,3,,,_]看出，好像是将输入的后面0、4和前面的2进行了换位，那么我们就要想到最经典的选择排序算法思想，用一个指针从头遍历寻找最大的元素，另一个指针去指向最大的元素应该在的位置，然后交换。因此应用到这道题目上，我们应该用一个指针i从头开始遍历寻找val，另一个指针从指向最后一个元素，即val应该待在的位置。

代码：

class Solution:def removeElement(self, nums: List[int], val: int) -> int:num_len = len(nums)j = num_len-1i = 0while j>=0 and nums[j]==val:j = j-1if j==-1:return 0while i < j:if nums[i]==val:nums[i],nums[j] = nums[j],nums[i]j = j-1while j >= 0 and nums[j] == val:j = j - 1i+=1for k in range(0, len(nums)):if nums[k]==val:return k

977.有序数组的平方

思路：

首先是暴力解法：直接将数组中每个元素都平方，然后一个排序，但是这样尽管使用快排，但是时间复杂度为O(nlogn)。而且元素大部分有序，快排的时间复杂度接近O(n^2)。那么堆排？那也是O(nlogn)。那么如何达到进阶的要求：设计时间复杂度为 O(n) 的算法解决本问题。那我们继续看最终平方的数组，前半部分倒序，后半部分正序，那这不久是一个只排一次的归并排序吗？OK，我们只需要把第一个数组倒着遍历即可。

代码：

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:nums1 = []nums2 = []for i in nums:if i < 0:nums1.append(i*i)else:nums2.append(i*i)len1 = len(nums1)len2 = len(nums2)i = len1-1j = 0k = 0while i>=0 and j<len2:if nums1[i]<nums2[j]:nums[k] = nums1[i]k+=1i-=1else:nums[k] = nums2[j]k+=1j+=1while i>=0:nums[k] = nums1[i]k+=1i-=1while j<len2:nums[k] = nums2[j]k+=1j+=1return nums