门户网站如何增加流量,杭州做网站工作室,网站建设亻金手指排名十五,htm网站上一篇:算法随笔_35: 每日温度-CSDN博客 题目描述如下:
给你一个长度固定的整数数组 arr #xff0c;请你将该数组中出现的每个零都复写一遍#xff0c;并将其余的元素向右平移。
注意#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改…上一篇:算法随笔_35: 每日温度-CSDN博客 题目描述如下:
给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。
注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。
示例 1
输入arr [1,0,2,3,0,4,5,0]
输出[1,0,0,2,3,0,0,4]
解释调用函数后输入的数组将被修改为[1,0,0,2,3,0,0,4] 算法思路:
这道题如果没有后边的条件(需要原地修改数组) 比较容易解决。我们可以新开辟一段同样长度的数组res然后定义两个指针p1, p2p1指向原数组首元素p2指向res数组首元素。然后从右往左枚举原数组arr。如果访问到的arr[p1]不为0那么把arr[p1]赋值给res[j]然后j向右移动一格。如果访问到的arr[p1]为0那么连续j向右移动两格每个格都赋值为0。以此类推直到p2到达数组res末尾。
但如果需要原地修改数组就需要多想想再仔细分析一下这道题。
我们发现还用上面的方法直接在原数组修改当遇到0的时候p2指针会覆盖两个格子的元素。碰到越多0覆盖的原值就越多。由于p2指针走的快导致当p1访问的时候一些原值已经不复存在。这个问题如何解决呢
我们发现由于p2比p1走的快当p2到达数组末尾时p1还未到达末尾。也就是说p1到p2这段的元素是不需要p1访问的最终的结果数组也用不到这些元素。所以我们可以考虑从右往左修改数组。具体的操作如下:
1. 设结尾索引end_ind。我们从左往右枚举数组arr索引值存于变量i。碰到值为非0的元素end_ind加1。碰到值为0的元素end_ind加2。直到end_ind大于等于数组长度退出。此时变量i就是需要保留的所有元素的最大索引。
2. 设变量j为数组的最后一个索引。
3. 我们从索引i处从右往左枚举数组arr。如果arr[i]不为0我们把arr[i]赋值给arr[j]然后j左移一格。如果arr[i]为0我们把j连续向左移动两格每个格都赋值为0。同时i也左移一格。当i小于0时退出枚举程序完成。
这里有个细节需要补充一下有可能end_ind大于数组长度。比如arr[1,0]end_ind3。由于长度肯定不能超过原数组长度。因此在步骤2的时候我们需要先判断一下如果end_ind大于数组长度需要把最后一个元素设为0。ij各自减1然后再运行步骤3。
此算法时间复杂度为O(n) 。下面是代码实现:
class Solution:def duplicateZeros(self, arr):arr_len len(arr)end_ind0i0while i arr_len:numarr[i]if num0:end_ind2else:end_ind1if end_indarr_len:breaki1jarr_len-1if end_indarr_len:arr[j]0j-1i-1while i 0:arr[j]arr[i]j-1if arr[i]0:arr[j]0j-1i-1
