关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3

关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3

方法2

方法2:遍历数组,遇到重复元素直接删掉。最后得到的数组的长度就是返回值。时间复杂度O(n2), 每次vector erase的代价都是O(n).

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

方法3

方法3:遍历数组,出现不相等元素就将该元素陆续存到数组的前面,j为数组下标。就在原数组上面改,之所以可以这么处理,因为j是肯定跑不过i的。时间复杂度O(n). [aabccd] its index as i [abcd] its index as j

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

别人给的都不是自己的,自己拿到的才是自己的,bring your own candy, 加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)请注明Leetcode刷题交流

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-09-29

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1074 食物链 2001年NOI全国竞赛

1074 食物链 2001年NOI全国竞赛 时间限制: 3 s 空间限制: 64000 KB 题目等级 : 钻石 Diamond 题目描述 Des...

3556
来自专栏HansBug's Lab

2748: [HAOI2012]音量调节

2748: [HAOI2012]音量调节 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 719  Solve...

3028
来自专栏斑斓

哲思片段 | 设计中的变与不变

古希腊哲学家巴门尼德认为:“人的思想和言语都有一个载体,如果你在这一时间和另外一个时间想到或者谈到同样一件东西,那就说明这件东西在这段时间内没有变化,如有变化的...

4007
来自专栏专知

【LeetCode 136】 关关的刷题日记33 Intersection of Two

关关的刷题日记33 – Leetcode 349. Intersection of Two Arrays 题目 Given two arrays, write ...

2975
来自专栏专知

关关的刷题日记10——Leetcode 1. Two Sum 方法1

关小刷刷题10 – Leetcode 1. Two Sum 方法1 题目 Given an array of integers, return indices ...

3089
来自专栏专知

关关的刷题日记05 —— Leetcode 219. Contains Duplicate II

关小刷刷题06 – Leetcode 219. Contains Duplicate II 题目 Given an array of integers and ...

3206
来自专栏菜鸟前端工程师

JavaScript学习笔记009-Json对象0解构赋值0扩展运算符

942
来自专栏数据结构与算法

2924 数独挑战

2924 数独挑战  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Descripti...

2953
来自专栏数据结构与算法

P1372 又是毕业季I

题目背景 “叮铃铃铃”,随着高考最后一科结考铃声的敲响,三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍,憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑...

3244
来自专栏专知

【 关关的刷题日记53】 Leetcode 100. Same Tree

关关的刷题日记53 – Leetcode 100. Same Tree 题目 Given two binary trees, write a function ...

3307

扫码关注云+社区

领取腾讯云代金券