LintCode 521.去除重复元素

时间:2022-08-25 08:01:11

LintCode 521.去除重复元素

描述

给一个整数数组,去除重复的元素。

你应该做这些事

1.在原数组上操作

2.将去除重复之后的元素放在数组的开头

3.返回去除重复元素之后的元素个数

挑战

1.O(n)时间复杂度.

2.O(nlogn)时间复杂度但没有额外空间

答案

  • 使用Map存储。时间复杂度O(n),空间复杂度O(n)

    public int deduplication(int[] nums) {
    // write your code here
    HashMap<Integer, Integer> map = new HashMap<>();
    int i = 0, j = nums.length - 1;
    while (i <= j) {
    if (map.get(nums[i]) == null) {
    map.put(nums[i], 1);
    } else {
    map.put(nums[i], map.get(nums[i]) + 1);
    }
    if (map.get(nums[i]) > 1) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
    j--;
    } else {
    i++;
    }
    }
    return map.size();
    }
  • 排序后用双指针

    public int deduplication(int[] nums) {
    Arrays.sort(nums); int i = 0, j = 1;
    while (j < nums.length) {
    if(nums[j] != nums[i]) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
    }
    j++;
    }
    return i+1;
    }

LintCode 521.去除重复元素的更多相关文章

  1. Python列表去除重复元素

    主要尝试了3种列表去除重复元素 #2.去除列表中的重复元素 #set方法 def removeDuplicates_set(nums): l2 = list(set(l1)) #用l1的顺序排序l2 ...

  2. java集合 collection-list-ArrayList 将自定义对象作为元素存到ArrayList集合中,并去除重复元素。

    import java.util.*; /* 将自定义对象作为元素存到ArrayList集合中,并去除重复元素. 比如:存人对象.同姓名同年龄,视为同一个人.为重复元素. 思路: 1,对人描述,将数据 ...

  3. php将多个值的数组去除重复元素

    array_unique(array) 只能处理value只有单个的数组. 去除有多个value数组,可以使用如下函数实现: function more_array_unique($arr=array ...

  4. ArrayList去除重复元素(多种方法实现)

    package other; import java.util.ArrayList; import java.util.HashSet; public class test4 { public sta ...

  5. &lbrack;C&plus;&plus;&rsqb;vector去除重复元素

    #include <iostream> #include <vector> #include <algorithm> #include <set> us ...

  6. ArrayList去除重复元素(包括字符串和自定义对象)

    1.去除重复字符串 package com.online.msym; import java.util.ArrayList; import java.util.Iterator; @SuppressW ...

  7. 使用HashSet&lt&semi;&gt&semi;去除重复元素的集合

    比如,某一个阵列中,有重复的元素,我们想去除重复的,保留一个.HashSet<T>含不重复项的无序列表,从MSDN网上了解到,这集合基于散列值,插入元素的操作非常快. 你可以写一个方法: ...

  8. ArrayList去除重复元素

    去除一个ArrayList的重复元素有两种方法:(ArrayList与Vector的存储结构是Object[],LinkedList是双向列表) 第一种是不需要借助临时list,用equals方法比较 ...

  9. C&plus;&plus; - 部分STL容器如何去除重复元素

    如果元素被保存在vector中,可先对vector里面的元素排序,然后调用unique函数去重,unique(起始迭代器,终止迭代器),返回的是去重以后vector中没有重复元素的下一个位置的迭代器. ...

随机推荐

  1. 批量创建10个用户stu01-stu10

    1.批量创建10个用户stu01-stu10,并且设置随机8位密码,要求不能用shell循环(例如:for,while等),只能用命令及管道实现. ##方法1: [root@server tmp]# ...

  2. WP8 双击返回键退出

    bool isExit = false; // 构造函数 public MainPage() { InitializeComponent(); isExit = false; // 用于本地化 App ...

  3. connect函数详解

    不得不说,客户端的connect函数和服务端的accept函数是一对好基友,如果客户端没有去connect, 那么服务端的accept会一直在那里傻傻地痴痴地等待,我们先来看看connect函数的原型 ...

  4. MySQL 大表优化方案

    当MySQL单表记录数过大时,增删改查性能都会急剧下降,可以参考以下步骤来优化: 单表优化 除非单表数据未来会一直不断上涨,否则不要一开始就考虑拆分,拆分会带来逻辑.部署.运维的各种复杂度,一般以整型 ...

  5. TTL集成门电路

    一.TTL集成门电路的结构1.总体结构 所谓TTL就是transistor transistor logic,就是说是由晶体管和晶体管之间构成电路. 2.    TTL集成门电路典型输入级形式 1)二 ...

  6. mysql 单表更新记录UPDATE

    1.单表更新 (1)mysql> SELECT * FROM users;+----+----------+----------+-----+------+| id   | username | ...

  7. 022&lowbar;applescript快速入门教程

    基础语法 一.这部分介绍注释,发出声音,弹窗 (1)简单入门 <1>多行注释 (* this is multi comment *) <2>发出响声 beep 3 (2) #表 ...

  8. ibatis &lpar;mybatis&rpar; for循环拼接语句【转】

    使用 , 拼接 查询条件dto public class queryCondition{ private String[] stuIds; private String name;} 查询sqlMap ...

  9. 三层和MVC

    一样写啊... 比如DAL层: C# code? 1 2 3 4 5 Public void Update(XXXXX.Models.News model) {         db.Entry(XX ...

  10. delphi CreateAnonymousThread 匿名线程

    引用  http://www.cnblogs.com/del/archive/2011/05/18/2049913.html 先看一个非多线程的例子, 代码执行时不能进行其它操作(譬如拖动窗体): { ...