首页 > ACM题库 > LeetCode > LeetCode-Remove Duplicates from Sorted Array[数组]
2014
11-19

LeetCode-Remove Duplicates from Sorted Array[数组]

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 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].

标签: Array Two Pointers
分析

代码1

// LeetCode, Remove Duplicates from Sorted Array
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (n == 0) return 0;

        int index = 0;
        for (int i = 1; i < n; i++) {
            if (A[index] != A[i])
                A[++index] = A[i];
        }
        return index + 1;
    }
};

代码2

// LeetCode, Remove Duplicates from Sorted Array
// 使用STL,时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        return distance(A, unique(A, A + n));
    }
};

代码3

// LeetCode, Remove Duplicates from Sorted Array
// 使用STL,时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        return removeDuplicates(A, A + n, A) - A;
    }

    template<typename InIt, typename OutIt>
    OutIt removeDuplicates(InIt first, InIt last, OutIt output) {
        while (first != last) {
            *output++ = *first;
            first = upper_bound(first, last, *first);
        }

        return output;
    }
};

相关题目
Remove Duplicates from Sorted Array II


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。