注册 登录
编程论坛 C++教室

二维表重复行查询

peach5460 发布于 2012-07-26 18:26, 1033 次点击
表定义:
vector<vector<cstring>> vecTable;

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

补充说明:
1,Table的行排列无规律...
2,不要用两个For循环嵌套,然后一个个遍历...这个时间复杂度是指数级的,我受不了...
3,不管是基于算法,或者基于c++语言特性优化都行,我只要快,并且无错...
4,我没答案,别问我,这是我目前碰到的头疼的问题...
5 回复
#2
pangding2012-07-26 20:37
排序的复杂度你受得了吗?还是不许排序?这个二维表大概是几乘几的维数?
#3
peach54602012-07-27 08:16
大约几千行到几万行,十到二十列...

我觉得困难,一是因为乱序,二是因为感觉最简单的写两个for遍历查找,逻辑很清晰,但是直觉上觉得会很慢(我没测过)
另外,排序倒不要紧,但是写个二维表排序也蛮头疼撒
#4
pangding2012-07-27 11:32
不用写二维表的排序呀,你不是比较行吗。那行内的数据就不用动,整行交换就行了,只是个一维的排序。

另外我还想了个方法,根据你数据的特点,如果能找一种效果还好 hash 算法,用开链存,STL 库里就有。冲撞的 hash 值再去检查一下是不是真的两行一样你看行不行。
#5
peach54602012-07-27 11:50
hash冲撞我昨晚躺床上睡觉时想过,应该比两个for好一点,我就在想,还有没更好的办法
#6
rjsp2013-08-09 16:48
用set等效率很低,因为set要保持时刻有序,对于你的需求而言这是不必要的效率浪费
用set的话,效率只是比“两个For循环嵌套”好一点,之所以好一点是因为set中元素是有序的,相当于第二个For使用了二分查找法进行加速

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

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

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

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

这其实就是快速排序算法
1