杨行网站建设,网络广告公司,企业网站有什么,wordpress留言的小伙伴题目#xff1a;
给定一个数组 num #xff0c;编写一个函数将数组内部的数字0都移动到数组的末尾#xff0c;同时保持非零元素的相对顺序#xff01;
同时不能通过复制数组#xff0c;开辟新的数组空间的情况下原地对数组进行操作
示例#xff1a; 本题的原理#x…题目
给定一个数组 num 编写一个函数将数组内部的数字0都移动到数组的末尾同时保持非零元素的相对顺序
同时不能通过复制数组开辟新的数组空间的情况下原地对数组进行操作
示例 本题的原理 本题的特点就是给定一个数组让我们直接在数组上进行操作将数组进行划分或者把数组分区这类操作
双指针算法 使用两个指针cur、dest将数组划分成三块区域待处理区域、非0区域、元素0区域 让指针在移动的同时保持三个区域不进行改变那么当待处理区域消失后整个数组就会变成非0区域和元素0区域。 cur将区域划分为处理过的区域和待处理的区域 dest将处理过的区域划分为非0区域和元素0区域 算法解析 两个指针的初始位置因为dest要区分非0和0但一开始并没有非0划分的区间不存在所以放到-1位置其次是先后因为cur是扫描指针所以先让cur指针进行移动而cur指针在扫描的时候会遇到两种情况一种是遇到0一种是遇到非0 而不论遇到什么我们都需要保持三个区间同时存在所以这里遇到0直接让cur移动一位保持三个区间同时存在 cur的右边是待处理dest1和cur-1是0 0到dest是非0而如果遇到了非0元素则我们要让这个元素加入到非0区间也就是0到dest的区间中所以先将dest往后移动1位让cur和dest的指针指向的元素进行交换后cur在往前移
总结
遇到0元素cur遇到非0元素swap(dest1cur);dest,cur;
代码编辑 解析
这里for中的cur配合了下面的if如果遇到0元素向前移动在这里指的是如果没有出发if中的非0条件自动
如果触发到了if中的非0条件直接dest向前移动 然后交换其中dest向前移动写在了交换内容中而遇到非0时dest和cur中的cur是写在了for中
