提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

每日一练：删除有序数组中的重复项

数组 删除 重复 每日 有序
2023-06-13 09:18:27 时间

注：这里一共有两道题，比较类似，我就把他们合并在一起讲！

删除删除有序数组中的重复项1

链接: 删除有序数组中的重复项1

毫无疑问，这道题要用双指针的方法，因为我们既要瞻前又要顾后！ 思路：

1、因为这道题要求让每个元素只出现一次，那么我们就先定义两个指针，一个叫tmp指向第一个数字，另一个叫cur指向第二个数字。 2、然后每次判断一下tmp与cur是否相等，若相等则让cur++，直到找到两个不相等的位置，然后让tmp++，接着让cur处的数字赋给tmp处。 3、cur继续加加，直到出了这个数组为止。

思路比较清晰，我们直接上代码：

int removeDuplicates(int* nums, int numsSize){
    int cur = 1;
    int tmp = 0;

    while(cur < numsSize)
    {
        if(nums[cur] == nums[tmp])
        {
            cur++;
        }
        else
        {
            tmp++;
            nums[tmp] = nums[cur];
            cur++;
        }
    }

    return tmp + 1;
}

删除有序数组中的重复项2

链接: 删除有序数组中的重复项2

在写这道题时候，一开始我是这么想的思路 （思路会比等会讲的第二种复杂，所以读者若不想听的话可以直接看第二种） ：

1、和第一题一样，先定义两个变量tmp和cur分别用来指向数组第一个数字和第二个数字，然后再定义一个变量k来计算等会重复超过了两次后，多的数。 2、开始循环，判断nums[cur]和nums[tmp] 是否相等，若不相等则让k置为0，若相等则让k加一，然后判断k是否大于等于2，若是则进入子循环对数组进行操作。最后让cur和tmp都加加。 3、若进入子循环，说明这是重复超过两次的数。首先我们先定义个变量num，用于记算一共重复超过多少个数，然后用while循环让cur向后走直到遇到不是这个重复的数。 如果这个时候已经出界了，则直接break返回tmp + 1即可。 若没有出界，再定义一个变量p，记录需要向前挪动多少个数据，即为numsSize - cur。然后用while循环将nums[cur] 处的数据赋给nums[cur - num] 处，循环p次。 最后将cur归位，将numsSize减掉num，再将k置为0。

从步骤就看得出来这种思路比较复杂hhh，但是比较直接一点，有兴趣的读者可以看下代码，没兴趣可以看第二种了hhh：

int removeDuplicates(int* nums, int numsSize){
    int cur = 1;
    int tmp = 0;
    //k用来计算重复超过了两个数后多的数
    int k = 0;
    
    while(cur < numsSize)
    {
        if(nums[cur] == nums[tmp])
        {
            k++;
            if(k >= 2)
            {
                int num = 0;
                while((cur < numsSize) && (nums[cur] == nums[tmp]))
                {
                    num++;
                    cur++;
                }
                //判断一下此时cur会不会出界，会直接break
                if(cur >= numsSize)
                    break;

                //p用来计算需要向前挪动多少个数据
                int p = numsSize - cur;
                while(p > 0)
                {
                    nums[cur - num] = nums[cur];
                    cur++;
                    p--;
                }
                cur = tmp + 1;//记得将cur归位
                numsSize -= num;//记得将总个数减少，防止后面的循环越界
                k = 0;
            }
        }
        else
        {
            k = 0;
        }
        cur++;
        tmp++;
    }

    return tmp + 1;
}

好啦进入正题！

在我兴高采烈的写完题后，我去看了一下别人的题解，突然发现，别人只写了几行的代码┭┮﹏┭┮，于是我决定修改我上面的思路，就是简化。

思路：

1、我们先定义两个变量cur 和 tmp，但是这次不同的是，tmp指向数组的第二个数字，cur指向tmp的下一位。

2、接着判断一下数组是否只有一个数字或者两个数字，若是的话直接返回tmp。

3、若前面判断不是只有两个数字以下的数组，则开始遍历cur，直到cur超出了数组的范围。

4、遍历过程中，每次判断一下cur处的数字是否与tmp以及tmp - 1位置的数字相等，若相等则说明重复超过了两次，则让cur++，直到不相等。若不相等了，先让tmp++，然后把cur处的数据赋给tmp处，然后cur++，继续遍历，直到结束。

int removeDuplicates(int* nums, int numsSize){
    int cur = 2;
    int tmp = 1;

    //如果数组只有一个或者两个数，则直接返回tmp
    if(cur >numsSize)
        return tmp;

    while(cur < numsSize)
    {
        if(nums[cur] == nums[tmp] && nums[cur] == nums[tmp - 1])
        {
            cur++;
        }
        else
        {
            tmp++;
            nums[tmp] = nums[cur];
            cur++;
        }
    }
    return tmp + 1;
}

这一看是不是就比上面第一种方法思路简洁多啦，而且思路也不复杂，只是一次性拿cur与tmp以及tmp的前一位比较是比较难想到的。

规律总结

类似这种”删除有序数组中的重复项“的题，其实本质就是最多保留n项重复数字，基本都是运用双指针的方法解决。 不仅如此，对于这类题，保留n项重复数字，通过第一题和第二题的比较可以看出，有以下的规律：

1、题目要求最多保留n项重复，那就让tmp指向第n -1项（因为别忘了数组下标是从0开始的），然后让cur指向tmp的下一位。 2、在遍历cur过程中，只需要判断cur处与tmp以及tmp前n - 1项是否相等即可。

这个就是这种题的规律，可以拓展到最多保留3项、最多保留4项…以此类推。

相关文章