UDN-企业互联网技术人气社区

板块导航

浏览  : 8527
回复  : 40

[Web] 有一堆袜子,如何用最快速高效的算法来给袜子配对?

[复制链接]
蜡笔小新的头像 楼主
发表于 2014-5-6 08:20:36 | 显示全部楼层 |阅读模式
早上看到的一个很有意思的问题:
【问题描述】
昨天我在整理从洗衣店洗干净的一堆袜子,发现我用的方法非常不高效。我用了一个最简单的方法:拿到一只袜子,然后从头到尾去找另外一只袜子。用这种方法需要重复平均超过 n/2*n/4=n2/8 双袜子。
作为一个计算机科学家,我在想我应该怎么做?我立马就想到了根据尺寸颜色排序来得到一个复杂度为O(NlogN)的方法。
哈希或其他“非原地”的方法在这里不可取,因为我不可能复制袜子(要是可以的话就好了)。
因此,这个基本问题是:
给一堆袜子,总数 n 双,即包含 2n 只袜子(袜子是乱放的,即不是成对放的),假设每只袜子都有一个确定的且能和它配对的袜子,问:如何用最快最有效的算法找出每只袜子与之配对的另一个袜子,并且最多使用对数级别的额外空间?
如果答案能够考虑到下面的几个方面,我会非常高兴:(我希望答案能够考虑到下面的几个方面:)
  • 该算法要同样适用于巨大数量的袜子。
  • 现实中袜子数量不会很多,我和我配偶的袜子加起来不超过30双(我们俩的袜子非常容易区分,这可以被利用吗?)
  • 该问题是否等同于元素唯一性问题(Element distinctness problem)?
整理袜子,困扰好多年,各位有啥高见?


发表于 2014-5-6 12:30:28 | 显示全部楼层
找一只小狗搞定....
使用道具 举报

回复

蜡笔小新的头像 楼主
发表于 2014-5-6 14:22:11 | 显示全部楼层
NsGFr 发表于 2014-5-6 12:30
找一只小狗搞定....

确实高招~
使用道具 举报

回复

发表于 2014-5-7 16:36:40 | 显示全部楼层
干嘛要配对啊...
懒人法则1: 一次买一批一模一样的袜子;
懒人法则2: 一次洗一批一模一样的袜子;
懒人法则3: 一次穿两只不一样的袜子.
问题解决.
使用道具 举报

回复

蜡笔小新的头像 楼主
发表于 2014-5-7 16:42:32 | 显示全部楼层
管理员 发表于 2014-5-7 16:36
干嘛要配对啊...
懒人法则1: 一次买一批一模一样的袜子;
懒人法则2: 一次洗一批一模一样的袜子;

3最实用了
使用道具 举报

回复

发表于 2014-5-9 08:00:06 | 显示全部楼层

屌(mu)丝(you)程(nv)序(peng)员(you)做派.....

wahahahaha~~~~~~

使用道具 举报

回复

蜡笔小新的头像 楼主
发表于 2014-5-9 08:13:51 | 显示全部楼层
NsGFr 发表于 2014-5-9 08:00
屌(mu)丝(you)程(nv)序(peng)员(you)做派.....

wahahahaha~~~~~~

:Q难道就不能含蓄点么
使用道具 举报

回复

发表于 2014-5-9 08:25:06 | 显示全部楼层
蜡笔小新 发表于 2014-5-9 08:13
难道就不能含蓄点么

回归主题,单纯对于袜子来说:
1)定义袜子对象,重写hashcode,equals方法
2)map搞定

3) 我这不是算法,我这(shi)是(feng)做(ri)法(xia),哈哈哈

使用道具 举报

回复

蜡笔小新的头像 楼主
发表于 2014-5-9 11:18:47 | 显示全部楼层
其实 第一眼看成了 有一堆妹子
使用道具 举报

回复

发表于 2014-5-9 12:35:40 | 显示全部楼层
蜡笔小新 发表于 2014-5-9 11:18
其实 第一眼看成了 有一堆妹子

赶紧把你头像给换了!!!!!!!!

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部