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.去除重复元素的更多相关文章
-
Python列表去除重复元素
主要尝试了3种列表去除重复元素 #2.去除列表中的重复元素 #set方法 def removeDuplicates_set(nums): l2 = list(set(l1)) #用l1的顺序排序l2 ...
-
java集合 collection-list-ArrayList 将自定义对象作为元素存到ArrayList集合中,并去除重复元素。
import java.util.*; /* 将自定义对象作为元素存到ArrayList集合中,并去除重复元素. 比如:存人对象.同姓名同年龄,视为同一个人.为重复元素. 思路: 1,对人描述,将数据 ...
-
php将多个值的数组去除重复元素
array_unique(array) 只能处理value只有单个的数组. 去除有多个value数组,可以使用如下函数实现: function more_array_unique($arr=array ...
-
ArrayList去除重复元素(多种方法实现)
package other; import java.util.ArrayList; import java.util.HashSet; public class test4 { public sta ...
-
[C++]vector去除重复元素
#include <iostream> #include <vector> #include <algorithm> #include <set> us ...
-
ArrayList去除重复元素(包括字符串和自定义对象)
1.去除重复字符串 package com.online.msym; import java.util.ArrayList; import java.util.Iterator; @SuppressW ...
-
使用HashSet<;>;去除重复元素的集合
比如,某一个阵列中,有重复的元素,我们想去除重复的,保留一个.HashSet<T>含不重复项的无序列表,从MSDN网上了解到,这集合基于散列值,插入元素的操作非常快. 你可以写一个方法: ...
-
ArrayList去除重复元素
去除一个ArrayList的重复元素有两种方法:(ArrayList与Vector的存储结构是Object[],LinkedList是双向列表) 第一种是不需要借助临时list,用equals方法比较 ...
-
C++ - 部分STL容器如何去除重复元素
如果元素被保存在vector中,可先对vector里面的元素排序,然后调用unique函数去重,unique(起始迭代器,终止迭代器),返回的是去重以后vector中没有重复元素的下一个位置的迭代器. ...
随机推荐
-
批量创建10个用户stu01-stu10
1.批量创建10个用户stu01-stu10,并且设置随机8位密码,要求不能用shell循环(例如:for,while等),只能用命令及管道实现. ##方法1: [root@server tmp]# ...
-
WP8 双击返回键退出
bool isExit = false; // 构造函数 public MainPage() { InitializeComponent(); isExit = false; // 用于本地化 App ...
-
connect函数详解
不得不说,客户端的connect函数和服务端的accept函数是一对好基友,如果客户端没有去connect, 那么服务端的accept会一直在那里傻傻地痴痴地等待,我们先来看看connect函数的原型 ...
-
MySQL 大表优化方案
当MySQL单表记录数过大时,增删改查性能都会急剧下降,可以参考以下步骤来优化: 单表优化 除非单表数据未来会一直不断上涨,否则不要一开始就考虑拆分,拆分会带来逻辑.部署.运维的各种复杂度,一般以整型 ...
-
TTL集成门电路
一.TTL集成门电路的结构1.总体结构 所谓TTL就是transistor transistor logic,就是说是由晶体管和晶体管之间构成电路. 2. TTL集成门电路典型输入级形式 1)二 ...
-
mysql 单表更新记录UPDATE
1.单表更新 (1)mysql> SELECT * FROM users;+----+----------+----------+-----+------+| id | username | ...
-
022_applescript快速入门教程
基础语法 一.这部分介绍注释,发出声音,弹窗 (1)简单入门 <1>多行注释 (* this is multi comment *) <2>发出响声 beep 3 (2) #表 ...
-
ibatis (mybatis) for循环拼接语句【转】
使用 , 拼接 查询条件dto public class queryCondition{ private String[] stuIds; private String name;} 查询sqlMap ...
-
三层和MVC
一样写啊... 比如DAL层: C# code? 1 2 3 4 5 Public void Update(XXXXX.Models.News model) { db.Entry(XX ...
-
delphi CreateAnonymousThread 匿名线程
引用 http://www.cnblogs.com/del/archive/2011/05/18/2049913.html 先看一个非多线程的例子, 代码执行时不能进行其它操作(譬如拖动窗体): { ...