首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >去除有序数组中重复元素的 3 种方法,快来瞧瞧吧

去除有序数组中重复元素的 3 种方法,快来瞧瞧吧

作者头像
村雨遥
发布2020-06-19 12:33:52
2.2K0
发布2020-06-19 12:33:52
举报
文章被收录于专栏:JavaParkJavaParkJavaPark

1. 问题描述

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

示例

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

2. 解决思路

2.1 数组原地操作

/**
* 去除有序数组中重复元素并返回数组的新长度
* @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;
}

2.2 普通方法

/**
* 去除有序数组中重复元素并返回数组的新长度
* @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;
}

2.3 双指针

/**
* 去除有序数组中重复元素并返回数组的新长度
* @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. 总结

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-06-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 村雨遥 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 2. 解决思路
    • 2.1 数组原地操作
      • 2.2 普通方法
        • 2.3 双指针
        • 3. 总结
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档