每天AC系列(十一):删除排序数组中的重复项

1 题目

LeetCode第26题,给出一个非降序的数组,删除重复的元素.

2 覆盖移动

题目明确要求不能使用额外的数组空间,一开始,没想到什么好的算法.
但是,它又有提示,不需要考虑数组中超出新长度后面的元素,所有,就想到了覆盖移动这样的方法.
思想很简单,就是使用两个下标,一个下标表示要返回的下一个要被替换的数,同时这个下标加1代表要返回的长度,一个下标为遍历数组的下标.
首先,遍历数组,若遇到大于nums[index]的数,首先判断当前下标是否为index的下一个,如果是下一个的话覆盖相当于重复了,把自己赋给自己,若i与index的距离大于1,则在自增index的同时,把i处的值覆盖到index处,这样就不用移动后面的数了,而且可以保证这样的数有序,最后返回index+1,表示不重复的元素的个数,即新数组的长度.

int index = 0;
for(int i=1;i<nums.length;++i)
{
    if(nums[i] > nums[index])
    {
        if(i > ++index)
            nums[index] = nums[i];
    }
}
return index+1;

嗯,一次就AC,舒服.
其他解法?不清楚,看了别人的题解差不多都是这样的,不过叫法不一样,叫双指针,快慢指针,本质都是一样.

4 再来一题

实在没想到上一题这么不堪一击,然后下一题是LeetCode的27题,与上一题有点类似,给定一个数组,删除数值等于指定值的所有元素.

5 解法

int index = -1;
for (int i = 0; i < nums.length; ++i) 
{
    if(nums[i] != val)
    {
        if (i > ++index)
            nums[index] = nums[i];
    }
}
return index + 1;

还是一样的解法啊,覆盖移动,快慢指针,这是上次的代码改了if的判断条件,然后就:

不想说什么了.

6 源码

github

码云