删除排序数组中的重复项

 

题目描述

   给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

题目解析

1、首先我们需要明白什么是原地算法(in-place algorithm),它是一种使用小的,固定数量的额外之空间来转换资料的算法。

2、给定的数组是有序的,不管是升序还是降序,重复出现的元素只可能在相邻的元素上

题目解答

算法1,时间复杂度o(n²)直接上代码,如下:

 

int process(int * nums,int numsSize)
{
 int saveNum=numsSize;
 for(int i=numsSize-1;i>0;i--)
 {
     if(nums[i]==nums[i-1])
     {
         for(int j=i-1;j<saveNum-1;j++)
         {
           nums[j]=nums[j+1];
         }
          saveNum--;
     }
 }
 return saveNum;
}
}

 

解题思路:有重复元素,我们就删除重复元素。数组中删除元素是数组的基本操作,这个我们都很熟悉,唯一需要注意的是元素删除后数组的长度会变短,因此我们需要注意循环的结束条件。我们使用两层循环,外层循环遍历数组,内层需要执行数组元素的删除操作;由于是删除操作,因此外层循环我们要采用倒叙的方式进行遍历,内层循环开始点为要删除的元素的索引,结束点为当前数组所剩余的长度。最后,返回剩余元素的个数。

算法2,时间复杂度o(n),代码如下:

int process(int* nums, int numsSize){
 int l=0;
 for(int i=0;i<numsSize;i++)
 {
     if(l<1||nums[l-1]!=nums[i])
    {
         nums[l++]=nums[i];
     }
 }
 return l;
}

解题思路:由于数组是有序的,因此我们用两个索引来遍历数组,第一个索引记录当前遍历过的数组的有限长度,用 l 表示,第二个索引记录当前遍历过的数组,用循环索引 i 表示。下标为i的元素和下标为l-1的元素,进行比较,不相等则将下标为i的元素赋值给下标为l的元素,此时有限数组的长度增加了,因此l要进行+1操作;如果相等,则l不动,i继续往下遍历,直至遍历完成。由于i首次遍历后,数组的有效长度肯定要加1,当时l-1为非法下标,因此l=0时的遍历,一定要将数组的有效长度 l 进行+1操作,for循环下的l<1的判断条件就是为了解决这个用例。

两种算法已经讲完了,欢迎指正批评

 

热门相关:地球第一剑   寂静王冠   无限杀路   横行霸道   战神