数组算法练习
2021/10/13 11:14:25
本文主要是介绍数组算法练习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
举一个字符数组的例子,如图所示:
二分查找:
算法的前提是数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。
写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。
循环不变量:在while或者for过程中,很多都是重复执行,比如while和for里面的判断。很多情况里面的判断条件都是不等式,那这个循环不变量就包括区间。比如[,)区间就包括右边界,那每次判断都不包括右边界。如果右边界是需要加进去判断的值,这样写就不可以。
java版二分法写法(左闭右闭):
class Solution { public int search(int[] nums, int target) { // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算 if (target < nums[0] || target > nums[nums.length - 1]) { return -1; } int left = 0, right = nums.length - 1;//right是包含的nums最后一个数值 while (left <= right) {//因为包含右边界,所以右边界是需要进行判断的,所以判断条件是<= int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1;//需要+1,中间值肯定不满足条件,所以已经判断过了 else if (nums[mid] > target) right = mid - 1; } return -1; } }
删除数组元素(双指针)
可能说了,多余的元素,删掉不就得了。
要知道数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
双指针的形式:1.fast指针比slow指针步数跨度大,例如slow一次1步,fast一次2步;解决链表环形入口
2.指针A和指针B从两边向中间移动,例如下面例题带负数有序平方排序问题
3.fast在slow前面一步,fast按一步步走,slow满足条件再走,相当远fast是一个探路的。slow做修改。比较有特点的就是删除数组元素
还有很多形式,还是需要更多的练习。
class Solution { public int removeElement(int[] nums, int val) { // 快慢指针 int fastIndex = 0; int slowIndex; for (slowIndex = 0; fastIndex < nums.length; fastIndex++) { if (nums[fastIndex] != val) { nums[slowIndex] = nums[fastIndex]; slowIndex++; } } return slowIndex; } }
带有负数有序平方再排序
一般整体排的话用快排,再平方时间复杂度n×log(n) + n
但是通过双指针,用过再在内存上开辟个存储地方,从两头比较A和B的平方大小,大的那个放到新开辟的地方,同时让指针大的那个移动,在比较,循环一边就可以做到了,时间复杂度就是n.
class Solution { public: vector<int> sortedSquares(vector<int>& A) { int k = A.size() - 1; vector<int> result(A.size(), 0); for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j,因为最后要处理两个元素 if (A[i] * A[i] < A[j] * A[j]) { result[k--] = A[j] * A[j]; j--; } else { result[k--] = A[i] * A[i]; i++; } } return result; } };
螺旋矩阵一写就废:
要时刻记得循环不变原则,按正方形的圈来,每次都是左闭右开。每次需要更新初始节点,和长度n
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去。
可以发现这里的边界条件非常多,在一个循环中,如此多的边界条件,如果不按照固定规则来遍历,那就是一进循环深似海,从此offer是路人。
这里一圈下来,我们要画每四条边,这四条边怎么画,每画一条边都要坚持一致的左闭右开,或者左开又闭的原则,这样这一圈才能按照统一的规则画下来。
class Solution { public int[][] generateMatrix(int n) { int[][] arr = new int[n][n]; int t = 1,mid = 0; int loop = n/2; int counter = 1; if(n%2 == 1){ arr[n/2][n/2] =n*n; } int startx = 0 ,starty = 0; while(loop > 0){ for(int x =startx,y = starty;y<starty + n-1;y++){ arr[x][y]=counter; counter++; } for(int y = starty + n - 1,x=startx;x <starty + n-1;x++){ arr[x][y]=counter; counter++; } for(int x = startx + n - 1,y=starty + n-1;y>startx;y--){ arr[x][y]=counter; counter++; } for(int y = starty,x=startx + n-1;x>startx;x--){ arr[x][y]=counter; counter++; } startx++; starty++; loop--;n=n-2; } return arr; } }
59. 螺旋矩阵 II
这篇关于数组算法练习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南