教育网站开发用例图,wordpress seo h1标签,杭州做网站找力果,呼叫中心外包导语
leetcode刷题笔记记录#xff0c;本篇博客记录数组基础1部分的题目#xff0c;主要题目包括#xff1a;
Leetcode 704 二分查找Leetcode 27 移除元素
知识点
二分查找
原理
二分查找的适用对象为有序数组且数组中无重复元素#xff0c;其主要原理是每次都从有序…导语
leetcode刷题笔记记录本篇博客记录数组基础1部分的题目主要题目包括
Leetcode 704 二分查找Leetcode 27 移除元素
知识点
二分查找
原理
二分查找的适用对象为有序数组且数组中无重复元素其主要原理是每次都从有序的区间中点开始对比数据因此其时间复杂度为 O ( l o g N ) O(logN) O(logN). 易错点
二分查找的易错点主要在边界条件的选取上比如while中到底使用还是中点位置索引mid更新时right middle呢还是要right middle - 1。为此可以使用区间的思想来理解。
一般我们在初始化左右边界时left0但right一般有两种常见的写法
right len(nums) - 1此时nums[right]是可以取到的是有意义的所以mid的取值为左闭右闭区间[left, right]。right len(nums)此时nums[right]无法取到是没有意义的所以mid的取值为左闭右开区间[left, right)。
对于第一种闭区间的情况由于左右都可以取到所以while中的判断条件应该是 left right而在更新right和left时则分别使用mid1mid-1即可。
对于第二种右侧为开区间的情况由于右边取不到边界值所以一定有left right所以在更新right时必须使用right mid。
双指针
原理 双指针Two Pointers指的是在遍历元素的过程中不是使用单个指针进行访问而是使用两个指针进行访问从而达到相应的目的。如果两个指针方向相反则称为「对撞指针」。如果两个指针方向相同则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表则称为「分离双指针」。 在数组的区间问题上暴力算法的时间复杂度往往是 O ( n 2 ) O(n^2) O(n2)。而双指针利用了区间「单调性」的性质可以将时间复杂度降到 O ( n ) O(n) O(n)。
Leetcode 704 二分查找
题目描述
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
示例 1:
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums [-1,0,3,5,9,12], target 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1提示
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
解法
主要的解题思路参考原理部分这里分别写出两种边界值取法下的代码。
左闭右闭解法
class Solution(object):def search(self, nums, target)::type nums: List[int]:type target: int:rtype: int# 首先定义左右索引值left, right 0, len(nums)-1while left right:# mid ( left right ) // 2mid ( right - left ) // 2 left # 避免溢出 if nums[mid] target:left mid 1elif nums[mid] target:right mid -1 else:return midreturn -1左闭右开解法
class Solution(object):def search(self, nums, target)::type nums: List[int]:type target: int:rtype: intleft, right 0, len(nums)while left right:mid ( right - left ) // 2 leftif nums[mid] target:return midelif nums[mid] target:left mid 1else:right mid return -1Leetcode 27 移除元素
题目描述
给你一个数组 nums **和一个值 val你需要 原地 移除所有数值等于 val **的元素并返回移除后数组的新长度。 不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1
输入 nums [3,2,2,3], val 3
输出 2, nums [2,2]
解释 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums [2,2,3,3] 或 nums [2,2,0,0]也会被视作正确答案。示例 2
输入 nums [0,1,2,2,3,0,4,2], val 2
输出 5, nums [0,1,4,0,3]
解释 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。提示
0 nums.length 1000 nums[i] 500 val 100
解法
这道题目由于规模不是很大首先可以使用暴力解法相关图示参考示意图
其中使用了两层循环复杂度为 O ( N 2 ) O(N^2) O(N2)。代码如下
class Solution(object):def removeElement(self, nums, val)::type nums: List[int]:type val: int:rtype: inti, cnt 0, 0size len(nums)while i size - cnt:if nums[i] val:for j in range(i, size-1):nums[j] nums[j1]cnt 1else:i 1return size - cnt之前讲到使用双指针可以将一些数组区间上的问题转化为 O ( N ) O(N) O(N)复杂度这里其实也可以使用快慢双指针来解决。我们定义两个指针一个快指针fast一个慢指针slow。一开始令两个指针都为0然后先移动fast如果nums[fast]不是要删除的值val那么移动slow然后将fast位置的值赋给slow位置。而如果nums[fast]是要删除的值val那么我们不管这个值继续移动fast。重复上述过程fast将遍历整个数组然后只将不是val的值移动到了前面而slow则记录了这些值的数目。所以返回值直接返回slow即可。
相关代码如下
class Solution(object):def removeElement(self, nums, val)::type nums: List[int]:type val: int:rtype: intslow, fast 0, 0size len(nums)while fast size:if nums[fast] ! val:nums[slow] nums[fast]slow 1fast 1return slow参考
代码随想录二分法双指针Two Pointers用法精讲及解题案例题解
