一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 719|回复: 10
收起左侧

[算法题] 优化Unique Characters?

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-15 19:04:25 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目在此:http://www.lintcode.com/en/problem/unique-characters/

这题虽然非常简单,想知道到底还能优化到什么程度。

非常容易就能用HashSet解决。

题目说,不用额外空间,那就想到用时间换空间,时间多点,o(n^2),就不需要额外空间。

想知道,这题,你们还能想到其他更优的不用额外空间的解法吗? 多谢讨论


我的代码在此链接的第47,48楼。http://www.1point3acres.com/bbs/thread-135921-3-1.html
2015fallcser 发表于 2015-6-15 19:19:25 | 显示全部楼层
对每个字母按照ASCII值排序
logarithmic: quicksort, mergesort
linear: radix sort了
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-15 21:07:20 | 显示全部楼层
2015fallcser 发表于 2015-6-15 19:19
对每个字母按照ASCII值排序
logarithmic: quicksort, mergesort
linear: radix sort了

感谢回复哈。

从你的回复,我巩固了 radix sort
https://en.wikipedia.org/wiki/Radix_sort
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-16 19:00:13 | 显示全部楼层
2015fallcser 发表于 2015-6-15 19:19
对每个字母按照ASCII值排序
logarithmic: quicksort, mergesort
linear: radix sort了

你能实现其中一种吗?java的就最好了。

我直接看代码比较直观。多谢啦
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-6-19 18:37:26 | 显示全部楼层
love1point 发表于 2015-6-16 19:00
你能实现其中一种吗?java的就最好了。

我直接看代码比较直观。多谢啦

mergesort之类的难道不是网上一抓一把么

不过   
string在java,python里面都是immutable的
所以并没有什么卵用
还是需要额外空间来排序
然后就大材小用搞复杂了  反而没什么意思
不如就hash了

其他我就不懂了哦  单纯看这个题目觉得好像没什么意思
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-19 18:41:13 | 显示全部楼层
2015fallcser 发表于 2015-6-19 18:37
mergesort之类的难道不是网上一抓一把么

不过   

用hash,需要额外空间

不用额外空间,双循环

我好奇,有没有,不需要额外空间,且时间复杂度是o(n)的
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-6-19 18:54:15 | 显示全部楼层
love1point 发表于 2015-6-19 18:41
用hash,需要额外空间

不用额外空间,双循环

不是说了么
immutable的,无法操作

如果是char[]的话,
排序一遍,去重一遍(这不就是hash么)
然后比较一遍  
最好的情况是linear  (O(2m+2n+min(m,n)))
不过真的感觉毫无毫无意义

当然可能有意义的我没想到  **表示就不乱指路了
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-19 19:27:40 | 显示全部楼层
2015fallcser 发表于 2015-6-19 18:54
不是说了么
immutable的,无法操作

谢谢回答。

我知道,我的好奇是问大家,给看这个帖子的其他人,我知道你已经回复我了,谢谢了
回复 支持 反对

使用道具 举报

kittycerry 发表于 2015-6-23 14:59:09 | 显示全部楼层
2015fallcser 发表于 2015-6-15 19:19
对每个字母按照ASCII值排序
logarithmic: quicksort, mergesort
linear: radix sort了

radix sort需要额外空间
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-23 17:58:00 | 显示全部楼层
kittycerry 发表于 2015-6-23 14:59
radix sort需要额外空间

你有啥好解法吗
回复 支持 反对

使用道具 举报

kittycerry 发表于 2015-6-23 23:13:53 | 显示全部楼层

不知道啊!所以才跟帖进来看
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 22:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表