leetcode 26 Remove Duplicates from Sorted Array

简介: Remove Duplicates from Sorted ArrayTotal Accepted: 66627 Total Submissions: 212739 My Submissions                       Given a ...


Remove Duplicates from Sorted ArrayTotal Accepted: 66627 Total Submissions: 212739 My Submissions

                     

Given a sorted array, remove the duplicates in place such that each element appear onlyonce 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 nums = [1,1,2],

Your function should return length = 2, with the first two elements ofnums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length



64ms好像有点慢了,这个方法有点讨巧了,绕过了算法的部分,以后还是少写这样的代码,多练习算法

我的解决方案:

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        set<int> result;
        for(int i = 0;i< nums.size();i++)
        {
            result.insert(nums[i]);
        }
        nums.clear();
        set<int>::iterator iter = result.begin();
        for(;iter!=result.end();iter++)
        {
            nums.push_back(*iter);
        }
        return nums.size();
    }
};



class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int start=1,N = nums.size();
        if(N<=1) return N;
        for(int i=1;i<nums.size();i++) {
            if(nums[i]!=nums[i-1]){
                nums[start]=nums[i];
                start++;
            }
        }
        return start;
    }
};


一行代码的STL:

class Solution { public: int removeDuplicates(int A[], int n) { return distance(A, unique(A, A+n)); } };


int removeDuplicates(vector<int>& nums) {
    if(nums.size() <= 1) return nums.size();

    vector<int>::iterator it1,it2;
    for(it1=nums.begin(),it2=nums.begin()+1; it2 != nums.end();) {
        if(*it2 == *it1) it2=nums.erase(it2);
        else {it1++;it2++;}
    }

    return nums.size();
}   

python解决方案:

class Solution:
    # @param a list of integers
    # @return an integer
    def removeDuplicates(self, A):
        if not A:
            return 0

        newTail = 0

        for i in range(1, len(A)):
            if A[i] != A[newTail]:
                newTail += 1
                A[newTail] = A[i]

        return newTail + 1




相关文章
|
10月前
Leetcode 4. Median of Two Sorted Arrays
题目描述很简单,就是找到两个有序数组合并后的中位数,要求时间复杂度O(log (m+n))。 如果不要去时间复杂度,很容易就想到了归并排序,归并排序的时间复杂度是O(m+n),空间复杂度也是O(m+n),不满足题目要求,其实我开始也不知道怎么做,后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
28 0
|
10月前
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
37 0
Search in Rotated Sorted Array - 循环有序数组查找问题
Search in Rotated Sorted Array - 循环有序数组查找问题
63 0
LeetCode 167 Two Sum II - Input array is sorted(输入已排序数组,求其中两个数的和等于给定的数)
给定一个有序数组和一个目标值 找出数组中两个成员,两者之和为目标值,并顺序输出
76 0
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
37 6
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
33 4
|
1月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
60 2
|
1月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
31 7