Array---Remove Duplicates from Sorted Array——移除排序数

sixgo 发布于2019-08-14 17:06 / 2337人阅读

摘要：主要是因为数组已经是排好顺序的。如果不仔细看题目，把数组当作无序数组进行操作，时会显示超时。题目要求是不能申请二额外空间，如果提交时有申请额外空间，也是不通过的。比如对于数组，移除重复元素后为，起始数字为，而不能是其它数字。

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

思路：

（1）这道题其实很简单。主要是因为数组已经是排好顺序的。如果不仔细看题目，把数组当作无序数组进行操作，OJ时会显示超时。

（2）题目要求是不能申请二额外空间，如果提交时有申请额外空间，也是不通过的。

（3）还需要注意的一个地方是，数组中元素的位置不能改变。比如对于数组[1,1,1,4,5]，移除重复元素后为[1,4,5]，起始数字为1，而不能是其它数字。

（4）我们只需对对组遍历一次，并设置一个计数器，每当遍历前后元素不相同，计数器加1，并将计数器对应在数组中位置定位到当前遍历的元素。

算法代码实现如下：

public static int removeDuplicates(int[] A) {
    int len = A.length;
    if (len == 0)
        return 0;
    int count = 1;
    for (int i = 1; i < len; i++) {
        if (A[i] == A[i - 1]) {
            continue;
        }else{
            A[count] = A[i];
            count++;
        }
    }
    return count;
}

上面的解法是针对有序数组，如果是无序数组，应该如何解答？

思路：

（1）如果不允许申请额外空间，则可以先对数组进行排序，为了提高效率一般考虑使用快速排序，然后再参照上面有序数组进行操作；

（2）如果允许申请空间，则只需创建一个HashSet，遍历一次数组，通过contanins()方法进行判断就能得到结果。

（1）和（2）所对应代码如下所示（注：针对本文所示的题目，如果用下面代码进行OJ，（1）会超时，（2）会产生额外空间）：

不可以申请额外空间：

public static int removeDuplicates(int[] A) {
    int len = A.length;
    if (len == 0)
        return 0;

    quickSort(A, 0, len - 1);

    int count = 1;
    for (int i = 1; i < len; i++) {
        if (A[i] == A[i - 1]) {
            continue;
        } else {
            A[count] = A[i];
            count++;
        }
    }
    return count;
}

//快速排序

private static void quickSort(int[] table, int low, int high) {
    if (low < high) {
        int i = low, j = high;
        int vot = table[i];
        while (i != j) {
            while (i < j && vot <= table[j])
                j--;
            if (i < j) {
                table[i] = table[j];
                i++;
            }
            while (i < j && table[i] < vot)
                i++;
            if (i < j) {
                table[j] = table[i];
                j--;
            }
        }
        table[i] = vot;
        quickSort(table, low, j - 1);
        quickSort(table, i + 1, high);
    }
}

可以申请额外空间：（其中，HashSet的contains()方法是用来过滤重复元素的）

public static int removeDuplicates(int[] A) {
    int len = A.length;
    HashSet set = new HashSet();
    for (int i = 0; i < len; i++) {
        if (set.size() == 0) {
            set.add(A[i]);
        }
        if (!set.contains(A[i])) {
            set.add(A[i]);
        }
    }
    return set.size();
}

私有云海外云主机 sorted-array Duplicates Sorted sorted_set

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66422.html

[Leetcode] Remove Duplicates from Sorted Array 移除有

摘要：双指针法复杂度时间空间思路我们可以将不重复的序列存到数列前面，因为不重复序列的长度一定小于等于总序列，所以不用担心覆盖的问题。代码双指针法复杂度时间空间思路思路和上题一样，区别在于记录前两个遍历到的数字来帮助我们判断是否出现了第三遍。 Remove Duplicates from Sorted Array I Given a sorted array, remove the dupl...

kel 2019-08-14 12:30 评论0 收藏0
[LintCode/LeetCode] Remove Duplicates from Sorted

摘要：思路原数组长度为，则返回原数组长度不为，则至少有个元素。将所有不重复的数值赋给，而当和相等时，不做处理。最后返回的就是不同元素的个数，也是新数组的长度。只有在时，才对赋值。注意，每次初始化的时候要分两种情况，这就意味着从的时候开始遍历。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...

WalkerXu 2019-08-14 15:32 评论0 收藏0
leetcode 26 Remove Duplicates from Sorted Array

摘要：题目比较简单，就是找出数组不重复的数字，返回不重复的数字个数。无需删除重复数字，只需要保证数组的前位为不重复的个数字即可代码如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...

alaege 2019-08-14 18:07 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
leetcode刷题记录-【26 Remove Duplicates from Sorted Ar

摘要：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用额外空间的条件下完成。声明两个指针，为快指针，为慢指针如果遇到相同的数，那么就跳过，。给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组...

heartFollower 2019-08-19 11:46 评论0 收藏0