单县网站定制,事业单位门户网站建设包含内容,浙江融兴建设有限公司网站,wordpress特定页面重定向1. 什么是数组
数组是存放在连续内存空间上的相同类型数据的集合。 数组可以方便的通过下标索引的方式获取到下标下对应的数据。 C中二维数组在地址空间上也是连续的。
需注意#xff1a;
数组的下标从0开始。数组内存空间的地址是连续的。数组的元素是不能删的#xff0c…1. 什么是数组
数组是存放在连续内存空间上的相同类型数据的集合。 数组可以方便的通过下标索引的方式获取到下标下对应的数据。 C中二维数组在地址空间上也是连续的。
需注意
数组的下标从0开始。数组内存空间的地址是连续的。数组的元素是不能删的只能覆盖。
2. 二分查找
力扣题目链接 之前的题解704. 二分查找中有一些地方不够清晰此处补充说明。 数组为有序数组数组中无重复元素 - 考虑二分法
在计算mid时考虑数据溢出的可能应将mid (low high) / 2;写为 int mid left ((right - left) / 2); //防止溢出二分法根据选择的区间不同有两种解决方式分别为左闭右闭 [left, right] 和左闭右开 [left, right) 在左闭右闭 [left, right] 的情况下nums [right] 表示数组中最后一个元素while (left right) 要使用 因为 left right 是有意义的。且每次判断if (nums[mid] target) 后由于nums[mid] 一定不是target right 要赋值为 middle - 1right mid - 1;这表示下一次要查找的左区间结束下标位置为 middle - 1即区间为 [left, middle - 1]。 同理if (nums[mid] target)时 left 要赋值为 middle 1。 在左闭右开 [left, right) 的情况下nums [right] 无意义while (left right)中使用****因为 left right 在区间 [left, right) 是没有意义的。每次判断if (nums[mid] target) 后nums[mid] 不等于target 在左区间 [left, mid) 中继续寻找. 区间右开right更新为mid。 区间左闭if (nums[mid] target)时left 要更新为 mid 1
二分查找时间复杂度为 O(log n)
相关题目135. 搜索插入位置 补充之前题解35. 搜索插入位置-二分查找中表达不清晰的地方。 这道题存在四种情况
目标值在数组所有元素之前目标值等于数组中某一个元素目标值插入数组中的某一位置目标值在数组所有元素之后
与上一道题的差别在于134情况下的返回值。在左闭右闭 [left, right] 的情况下right mid - 1;1情况下此时 right -13情况下 right 指向应插入的前一个位置4情况下 right 指向最后一个元素的位置所以应返回 right 1 即return right 1;在左闭右开 [left, right) 的情况下right mid;所以应返回 right 即return right;。
相关题目269.x的平方根 367.有效的完全平方数 题解【LeetCode-简单】69.x的平方根 367.有效的完全平方数 - 二分法
相关题目3【LeetCode-中等】34. 在排序数组中查找元素的第一个和最后一个位置 - 二分法
3. 移除元素 - 双指针
力扣题目链接 题解【LeetCode-简单】27.移除元素 - 数组与双指针法
由于Leetcode中数组是用的vector这道题可以用nums.erase(it);函数暴力破解但要注意erase()函数在删除元素后会将位于该元素后方的剩余元素前移这将导致数组长度的改变以及后续元素下标的变化删除元素后迭代器 it 不需要 it便已经指向了下一个元素。
不考虑vector的因素由于数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖。本题可采用双指针的方法。 双指针法快慢指针法 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。 下面定义本题中的快慢指针
快指针寻找新数组不含有目标元素的数组的元素 即用于寻找不等于val的元素慢指针指向更新新数组下标的位置即指向需要被覆盖的等于val的元素
最终慢指针一定指向了最终数组末尾的下一个元素只要返回慢指针即可。 题目中提及元素的顺序可以改变同向双指针和相向双指针都可以使用如果要求不能改变元素顺序则应该使用同向双指针。
4. 有序数组的平方 - 双指针
力扣题目链接 典型的双指针问题暴力解法的时间复杂度是O(nlogn)而采用双指针的时间复杂度是O(n)。 题解【LeetCode-简单】977. 有序数组的平方-双指针
5. 长度最小的子数组 - 滑动窗口
力扣题目链接
题解【LeetCode-中等】209.长度最小的子数组-双指针/滑动窗口
所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。
在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环完成了一个不断搜索区间的过程。滑动窗口只用一个for循环来完成这个操作。
而这个循环的索引一定是表示 滑动窗口的终止位置。
直观的动画演示 滑动窗口的精妙之处在于根据当前子序列和大小的情况不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。 while (sum s) {subLength (j - i 1); //取子序列的长度result result subLength ? result : subLength;这里体现出滑动窗口的精髓之处不断变更i子序列的起始位置sum - nums[i]; }6. 螺旋矩阵II - 模拟
力扣题目链接 题解【LeetCode-中等】59.螺旋矩阵II - 二维数组
本题并不涉及到什么算法就是模拟过程还要注意边界情况。
