Loading...
墨滴

村雨遥

2021/11/09  阅读:12  主题:雁栖湖

【数据结构与算法】有序数组的去重算法

1问题

给定一个有序数组,要删除数组重复出现的元素,使得每个元素只出现一次,然后返回移除重复数组后的新长度;

示例

假设给定一个数组 nums = [1,2,4,4],删除重复出现的元素 4 后,原数组变成 nums = [1, 2, 4],此时新的数组长度为 3;

2解决思路

数组原地操作

数组原地操作,此时无需创建新的数组,只需要在原来的数组上操作即可。相当于首先要找到数组中重复的元素,然后将重复的元素移除,此时就涉及到数组中的删除操作,相关知识点可以看我的另一篇文章 数组的增删改查

这是一种时间换空间的方法,此时的空间复杂度为 ,时间复杂度为 ,具体实现可以参考如下代码,其中也详细注释了每一步操作。

/**
* 去除有序数组中重复元素并返回数组的新长度
@param nums
@return 删除重复元素后数组的新长度
*/

public int removeDuplicates(int[] nums) {
    // 数组初始容量
    int length = nums.length;

    // 我们假定数组最后一个元素是唯一的,然后对于其他的每个元素,如果自身与它后边的数相同,那么就删除这个相同的元素
    for(int i = length - 2; i >= 0; i++){
        // 比较当前元素与其后一个元素是否相等
        if(nums[i] == nums[i + 1]){
            // 若相等,则移除后一位,并将所有元素向前移动一位
            for(int j = i + 1; j < length; j++){
                num[j - 1] = nums[j];
            }
            length--;
        }
    }

    // 返回数组的新长度
    return length;
}

普通方法

针对数组原地操作算法时间复杂度为 ,为降低时间复杂度提高算法效率,可以通过空间换时间的做法,通过定义新的数组,从而实现去除重复元素的目的,此时的时间复杂度为 ,而空间复杂度也由 变成了 。但是有几点需要注意:

  1. 临界情况(即数组为空);
  2. 创建新数组时,需要指定其容量,所以需要先求出原数组中无重复元素时的元素个数;
  3. 最后则是将原数组中未重复的元素赋值给新数组;
/**
* 去除有序数组中重复元素并返回数组的新长度
@param nums
@return 删除重复元素后的新数组
*/

public int[] removeDuplicates(int[] nums) {
    // 临界情况
    if(nums.length == 0){
        return nums;
    }

    // 先求出数组中无重复时的元素个数
    int size = 0;
    for(int i = 0; i < nums.length; i++){
        if(i == 0 || nums[i] != nums[i - 1]){
            size++;
        }
    }

    // 用于存放不含重复元素的有序数组
    int[] resultArr = new int[size];

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

    // 返回新的不含重复元素的有序数组
    return resultArr;
}

双指针

以上的两种方法要么是以时间换空间,要么是以空间换时间,那我们有没有一种折中的办法,既能保证时间复杂度很低,也能保证空间复杂度呢?答案是:当然有!

利用双指针的思想,既可以将空间复杂度控制在 ,也可以将时间复杂度控制在

/**
* 去除有序数组中重复元素并返回数组的新长度
@param nums
@return 删除重复元素后数组的新长度
*/

public int removeDuplicates(int[] nums) {
  // 临界情况
    if(nums.length == 0){
        reutrn 0;
    }

    int size = 0;
    for(int i = 1; i < nums.length; i++){
        if(nums[size] != nums[i]){
            nums[++size] = nums[i];

        }
    }

    // 返回新长度
    return size + 1;
}

3总结

以上就是 3 种去除有序数组中重复元素的三种算法,其中既有以时间换空间的数组原地操作法,也有空间换时间的普通方法,最后的话则是有一种综合前两种方法优点的方法 - 双指针。通过双指针方法,既能保证空间复杂度为 ,也将时间复杂度限制在了

想不到连简单的数组去重都有这么大的学问,我们在日常学习时,大多可能只关注于如何实现功能即可。但如果要应用到工作场景中,可能就需要考虑效率问题,此时则需要根据我们的具体需求来进行选择了。

好了,以上就是今天的内容了,如果你还有其他更好的方法,欢迎留言交流呀!

村雨遥

2021/11/09  阅读:12  主题:雁栖湖

作者介绍

村雨遥

公众号:村雨遥