专栏首页村雨遥去除有序数组中重复元素的 3 种方法,快来瞧瞧吧

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

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. 总结

本文分享自微信公众号 - 村雨遥(cunyu1943),作者:村雨遥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 每日一题 1480. 一维数组的动态和

    “给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。

    村雨遥
  • LeetCode 905. 按奇偶排序数组

    905. 按奇偶排序数组: https://leetcode-cn.com/problems/sort-array-by-parity/

    村雨遥
  • LeetCode 每日一题 1486. 数组异或操作

    数组 nums 定义为:nums[i] = start + 2*i(下标从 0 开始)且 n == nums.length 。

    村雨遥
  • 恢复旋转排序数组

    一份执着✘
  • 100. 删除排序数组中的重复数字 双指针+替换

    给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度。 不要使用额外的数组空间,必须在原地没有额外空间的条件下完成。...

    和蔼的zhxing
  • Dimple在左耳听风ARTS打卡(第九期)

    所谓ARTS: 每周至少做一个LeetCode的算法题;阅读并点评至少一篇英文技术文章;学习至少一个技术技巧;分享一篇有观点和思考的技术文章。(也就是Algor...

    程序员小跃
  • LeetCode题组:第26题-删除排序数组中的重复项

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。(注意这里提到了排序数组,也就是说数组是有序的。如果无序,...

    明天依旧可好
  • LeetCode 189:旋转数组 Rotate Array

    Given an array, rotate the array to the right by k steps, where k is non-negativ...

    爱写bug
  • LeetCode 189:旋转数组 Rotate Array

    Given an array, rotate the array to the right by k steps, where k is non-negativ...

    爱写bug
  • leetcode-easy-array-删除排序数组中的重复项

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    shengjk1

扫码关注云+社区

领取腾讯云代金券