《算法通关村——双指针的妙用》

梦里梦外; 2024-02-20 09:08 58阅读 0赞

问题描述：LeetCode26给你一个有序数组nums，请你原地删除重复出现的元素，使得每个元素只出现一次，返回删除后数组的新长度。

要求：不要使用额外的数组空间，你必须在原地修改输入数组，并在使用O（1）额外空间的条件下完成

算法:首先我想到的是快慢双指针，slow指向有效数组，fast负责遍历

而且因为新数组的元素小于原始数组，直接用新的数覆盖掉重复数字即可

比如原来是【2 2 3】,当fast指向3时和slow-1的值不一致，直接用3覆盖掉2/，就不用另外设置新数组

这里为了减少不必要的操作令slow=1将比较对象换做是【slow-1】

假设按照正常来slow=0，比较对象是slow。那么fast就会将第二个不同的值赋值给slow【0】实际上会把第一个值遗漏，如果令slow等于1.那么在进入第一次不匹配时（nums【0】和nums【1】不同时），会将第一个值赋给slow，避免了上述问题。这个初始化确实很有意思，也算是容易出错的地方。

>     public static int removeDulicates(int[] nums){
>         int slow=1;//slow可以直接为，索引为0的元素不用管
>         for(int fast=0;fast< nums.length;fast++){
>             if(nums[fast]!=nums[slow-1]){
>                 nums[slow]=nums[fast];
>                 slow++;
>             }
>         }
>         return slow;
>     }

#### 类似的关于覆盖的想法； ####

题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。  
一.自己思路  
思路：从头到尾遍历，判断值为0从当前下标依次往后挪，同时遍历数减一（因为已知挪动后末尾为0），再从头遍历筛选0.  
缺点：时间复杂度高，每次都要重复遍历。算法错误，，目前还没找出来。先暂时把错误代码贴在这里。  
> void moveZeroes(int\* nums, int numsSize)\{  
int i=0,j=0,temp=0,sum=0;  
for(i=0;i<numsSize-sum;i++)\{  
if(nums\[i\]==0)\{  
sum++;  
for(j=i;j<numsSize-sum;j++)\{//一个个往后交换  
temp=nums\[i\];  
nums\[i\]=nums\[i+1\];  
nums\[i+1\]=temp;  
\}  
i--;  
\}  
\}  
\}  
二。别人的思路1  
算法：把非0的往前挪，挪完之后，后面的就都是0了，然后在用0覆盖后面的。  
void moveZeroes(int\* nums, int numsSize)\{  
//异常处理  
if(numsSize==0)  
return;  
int index=0;//index实际上是新数组的索引，有点双指针的思想  
for(int i=0;i<numsSize;i++)\{  
if(nums\[i\]!=0)  
nums\[index++\]=nums\[i\];//把非0的往前挪，因为原始个数要大于挪的个数，挪的过程不会把有效数据覆盖掉。  
\}  
//后面的都覆盖为0,我原本想的是统计出来0的个数numsSize-index，但只要从index继续往后覆盖到数组长度就可以了。  
while(index<numsSize)\{  
nums\[index++\]=0;  
\}  
\}  
\`\`\`