| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1033 人关注过本帖
标题:二维表重复行查询
只看楼主 加入收藏
peach5460
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:武汉
等 级:贵宾
威 望:30
帖 子:2780
专家分:6060
注 册:2008-1-28
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:5 
二维表重复行查询
表定义:
vector<vector<cstring>> vecTable;

需求:
找出任意两行所有字符串元素都一模一样的行...返回两个索引...
找到任意两个就可以退出了...
找不到则返回两个-1.

补充说明:
1,Table的行排列无规律...
2,不要用两个For循环嵌套,然后一个个遍历...这个时间复杂度是指数级的,我受不了...
3,不管是基于算法,或者基于c++语言特性优化都行,我只要快,并且无错...
4,我没答案,别问我,这是我目前碰到的头疼的问题...
搜索更多相关主题的帖子: 字符串 元素 
2012-07-26 18:26
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
排序的复杂度你受得了吗?还是不许排序?这个二维表大概是几乘几的维数?
2012-07-26 20:37
peach5460
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:武汉
等 级:贵宾
威 望:30
帖 子:2780
专家分:6060
注 册:2008-1-28
收藏
得分:0 
大约几千行到几万行,十到二十列...

我觉得困难,一是因为乱序,二是因为感觉最简单的写两个for遍历查找,逻辑很清晰,但是直觉上觉得会很慢(我没测过)
另外,排序倒不要紧,但是写个二维表排序也蛮头疼撒

我总觉得授人以鱼不如授人以渔...
可是总有些SB叫嚣着:要么给代码给答案,要么滚蛋...
虽然我知道不要跟SB一般见识,但是我真的没修炼到宠辱不惊...
2012-07-27 08:16
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:20 
不用写二维表的排序呀,你不是比较行吗。那行内的数据就不用动,整行交换就行了,只是个一维的排序。

另外我还想了个方法,根据你数据的特点,如果能找一种效果还好 hash 算法,用开链存,STL 库里就有。冲撞的 hash 值再去检查一下是不是真的两行一样你看行不行。
2012-07-27 11:32
peach5460
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:武汉
等 级:贵宾
威 望:30
帖 子:2780
专家分:6060
注 册:2008-1-28
收藏
得分:0 
hash冲撞我昨晚躺床上睡觉时想过,应该比两个for好一点,我就在想,还有没更好的办法

我总觉得授人以鱼不如授人以渔...
可是总有些SB叫嚣着:要么给代码给答案,要么滚蛋...
虽然我知道不要跟SB一般见识,但是我真的没修炼到宠辱不惊...
2012-07-27 11:50
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:0 
用set等效率很低,因为set要保持时刻有序,对于你的需求而言这是不必要的效率浪费
用set的话,效率只是比“两个For循环嵌套”好一点,之所以好一点是因为set中元素是有序的,相当于第二个For使用了二分查找法进行加速

比set更好的方法是排序,相当于去掉了set的“保持时刻有序”开销
但你的需求并不需要完整排序,所以完整排序也是一种浪费

对于Hash,我不多说,因为这取决于你的数据特征

一个利用std::sort的讨巧做法(但我并不建议你这么做),是在其第三个参数,即比较函数中,判断两值是否相等,若相等,抛出异常,你在外围捕获到异常即表明有数据重复

我觉得正规的做法,是算法和快速排序类似,但不排序,即:
a. 取出第一个元素,并将其余元素依次和其对比,
   若相等,找到并退出
   若小于,将这个元素放到左边的袋子
   若大于,将这个元素放到右边的袋子
   这样之后,就得到两个袋子,左边袋子中没有一个元素和右边袋子的元素相等,因此它们之间就不需要比较了
b. 递归左边的袋子
c. 递归右边的袋子

这其实就是快速排序算法
2013-08-09 16:48
快速回复:二维表重复行查询
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015591 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved