十万个数中如何找出两个不同的呢，高人指点下啊 前几天去面试，被人问如何从10万个数中找出两个重复的，我数据结构学的不好，跟人家说往哈希表里放，放到有重复程序就崩了，那样就知道了，结果被嘲笑了。那在数据结构中应该怎么找呢？ 解决方案 » 免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货 将10万个数放到 int[]test中,Dictionary<int, int> kk = new Dictionary<int, int>();for (int i = 0; i < 100000; i++){if (!kk.ContainsKey(test[i]))kk.Add(test[i],1);else输出"有重复数"+test[i];} Dictionary实际上底层还是调用的Hashtable，效率应该不会比Hashtable要高吧 和你说的还是有区别的.首先这是dictionary,不需要hash算法,不需要gethashvalue,不会有冲突处理另外你说的崩溃与if (!kk.ContainsKey()) 完全不可相提并论这是dictionary专门用于检测是否有相同键的方法,效率是拉近0(1)的,很高效. 1、先采用外部排序（就目前的内存来讲的话可以直接在内存中排序），然后再查找重复的；需要至少两次循环,但占用内存少，有时间换取了空间；2、如果真的很想省事儿的话，就直接放到IDictionary<>中去，add的时候注意try catch就可以了，这只需要一次循环，用空间换取了时间 人家问的会不会是数据库的问题?select num, count(num) from numTable group by num having count(num) >= 2考算法的话何必要从10万个数中去找呢?毕竟算法的话10个数和10万个数也没区别吧!个人愚见！ 标题是要找不同,内容是要找重复,不知道应该按照哪个来说!反正用dictionary肯定可以,时间复杂度也比较低,就是空间代价稍微高一些,不过10万也不算太大,绝对可以承受! 是不是人家考你的LINQ 查询啊 转一篇文章, 转自：http://hi.baidu.com/ecgql/blog/item/21a515469c79d90e6b63e5b8.html------------------------------------------------------------有10亿个整数，要求选取重复次数最多的100个整数要解答这个问题，首先要弄清楚下面几个条件。 （1）有内存限制吗？ （2）整数的范围是多少？有符号，无符号，32位还是64位？ （3）整数集的内容大吗？（即出现的整数空间的大小大吗？） （4）如果只需要求模糊解，怎么解？ （5）求数组中的第k大元素？ （6）相关问题：求一个整数列中出现次数最多的整数 （7）相关问题：有一个整数数组，请求出两两之差绝对值最小的值,记住，只要得出最小值即可，不需要求出是哪两个数。 （1）如果没有内存限制，且假设是32位无符号的整数。最方便的办法就是建立一个整形数组，int hash[2^32]（赞不考虑程序的虚地址空间上限），然后对这10亿个数进行一次遍历，这样，可以得到这2^32个数各自出现的次数，再对这个hash数组进行取第k大元素，100次后，就可以取出这出现次数最多的前100个数。遍历10亿个数的时间复杂度是O(n)，n=10^10，求第k大元素的时间复杂度是O(m)，m=2^32(=4294967296)，那么本算法的时间复杂度是O(n)，空间复杂度是O(s)，s=2^32。内存要2^32*4=16G （2）如果有内存限制，或者必须满足程序虚地址空间上限。那么可以对整数空间进行分段处理，比如只提供512M内存，则将2^32个整数划分成32个空间0~2^(27)-1，2^(27)~2^(28)-1，...，31*2^(27)~2^(32)-1。对原来的10亿个数遍历32次，每次遍历，得到每个空间的整数的出现次数，并求出此空间中，出现次数最多的前100个整数，保存下来。这样32次之后，就得到了出现次数前3200的整数，再对这3200个整数取第k大元素，得到出现次数最多的前100个整数。这个算法的时间复杂度也是O(n)，空间复杂度降低多少不知道，但是内存使用降低不少。 （3）如果整数空间比较小，也就是说这10亿个数中有很多重复的数，最方便的办法估计就是维护一个HashTable对象ht，key就是整数值，value就是该整数值出现的次数。遍历这10亿个元素，得到ht后再对这个ht求第k大元素。那么这个算法的时间复杂度就是O(n)，n=10^10，空间复杂度是O(m)，m为整数空间大小。 （4）随机采样（或者将原来的顺序打乱，然后再顺序采样）。对样本中的整数进行出现次数的统计，这个时候采用HashTable的办法最好，时间复杂度是O(n)。如果对使用的空间有所限制，那么只能对该样本进行排序，再对排序后的样本进行100次遍历得到出现次数最多的前100个整数，则时间复杂度是O(nlogn)，空间复杂度是O(1)。 （5）好像有两种算法。假设要求数组a[1...n]中第k大元素。 （a）递归快排算法。若n<44（经验值）则直接排序返回第k大元素，否则，将1到n分成n/5个组，每个组5个元素，然后求这n/5个组的每组的中项元素，再求这n/5个中项元素的中项元素mm（注意，这里也可以用递归调用自身的方法）。然后对数组a根据mm分成三组，a1中的所有元素小于mm，a2中的所有元素等于mm，a3中的所有元素大于mm，如果|a1|>=k，则第k大元素在a1中，如果|a1|+|a2|>=k|a1|,则第k大元素就是mm，如果k>|a1|+|a2|，则第k大元素在a3中，再继续递归调用。这个算法的时间复杂度是O(n)。（注意，这里的中项mm也可以随机选择a中的元素，其时间复杂度也近似于O(n)，而且系数也比较小）。 （b）基于位查找（仅对于无符号整数的查找）。将32位整数的二进制位分为4段，每段8位，先比较a中所有元素高8位，找出第k大元素高8位的范围，再对应这高8位的范围在次高八位中找第k大元素的范围，...这样4次之后就可以找到第k大元素的。可以举个例子便于理解，在10个3位整数中找第k大元素，将3位分成3段，每段1位，每位之可能是0，1。如果这10个数的最高位0的个数m大于等于k，则第k大元素的最高位为0，再在最高位为0的元素中找次高位为第k大元素；如果10个数中最高位0的个数m大于k，则在最高位为1的元素中找此高位为第m-k大元素。... （6）这个问题是前面那个问题的特例。有没有特殊的解法使效率又提高一些呢？我觉得没有，因为1和100本来就是常数级，和n比它们的差别是忽略不计的。 （7）简单的解法是对这个数组排序，然后再对排好序的数组进行一次遍历就可得到两两绝对值最差的最小值，时间复杂度是O(nlogn)。网上说求a的min，max和长度n，如果Dmax = (max-min+1)/n = 0，那么就说明数组a中有重复的元素，直接返回0。但是如果Dmax = (max-min+1)/n > 0,那么就以Dmax为箱的长度装入a的元素，再在箱内和箱间比较。我不懂为什么，但是这个空间复杂度是O(max)，而且好像如果a是1, 2, 3...100，那么Dmax就是1了，那么a不是没有动吗？还有人说够找数组b，b[i] = a[i] - a[i+1]，则a[i]-a[j]=b[i]+b[i+1]+...+b[j-1]也不知下文了，看来这个题比较搞啊。就是奥赛题，BS。 问的是不是数据库中查出重复的数据呀？ORACLE sql语句 select * from rowid not in(select max(rowid) from table_name group by colum1....) c#如何动态调用程序集 数据从DataSet导入到数据库 大家遇到过没有？ 急啊？兄弟些帮忙啊 关于SQL数据库的一个小白问题: 一个Process.StandardOutput.ReadToEnd()使用问题 c＃使用问题 请问在工作岗位的朋友!公司对c#的态度如何? c#就這麼難用嗎?關於數據庫 VC#真的不能在WIN98下用用吗？ 这样的问题应该怎么设计： 如何让Lable标签显示"\t"
for (int i = 0; i < 100000; i++)
{
if (!kk.ContainsKey(test[i]))
kk.Add(test[i],1);
else
输出"有重复数"+test[i];
}
Dictionary实际上底层还是调用的Hashtable，效率应该不会比Hashtable要高吧
和你说的还是有区别的.
首先这是dictionary,不需要hash算法,不需要gethashvalue,不会有冲突处理
另外你说的崩溃与if (!kk.ContainsKey()) 完全不可相提并论这是dictionary专门用于检测是否有相同键的方法,效率是拉近0(1)的,很高效.
select num, count(num) from numTable group by num having count(num) >= 2考算法的话何必要从10万个数中去找呢?毕竟算法的话10个数和10万个数也没区别吧!
个人愚见！
------------------------------------------------------------
有10亿个整数，要求选取重复次数最多的100个整数
要解答这个问题，首先要弄清楚下面几个条件。
（1）有内存限制吗？
（2）整数的范围是多少？有符号，无符号，32位还是64位？
（3）整数集的内容大吗？（即出现的整数空间的大小大吗？）
（4）如果只需要求模糊解，怎么解？
（5）求数组中的第k大元素？
（6）相关问题：求一个整数列中出现次数最多的整数
（7）相关问题：有一个整数数组，请求出两两之差绝对值最小的值,记住，只要得出最小值即可，不需要求出是哪两个数。 （1）如果没有内存限制，且假设是32位无符号的整数。最方便的办法就是建立一个整形数组，int hash[2^32]（赞不考虑程序的虚地址空间上限），然后对这10亿个数进行一次遍历，这样，可以得到这2^32个数各自出现的次数，再对这个hash数组进行取第k大元素，100次后，就可以取出这出现次数最多的前100个数。遍历10亿个数的时间复杂度是O(n)，n=10^10，求第k大元素的时间复杂度是O(m)，m=2^32(=4294967296)，那么本算法的时间复杂度是O(n)，空间复杂度是O(s)，s=2^32。内存要2^32*4=16G
（2）如果有内存限制，或者必须满足程序虚地址空间上限。那么可以对整数空间进行分段处理，比如只提供512M内存，则将2^32个整数划分成32个空间0~2^(27)-1，2^(27)~2^(28)-1，...，31*2^(27)~2^(32)-1。对原来的10亿个数遍历32次，每次遍历，得到每个空间的整数的出现次数，并求出此空间中，出现次数最多的前100个整数，保存下来。这样32次之后，就得到了出现次数前3200的整数，再对这3200个整数取第k大元素，得到出现次数最多的前100个整数。这个算法的时间复杂度也是O(n)，空间复杂度降低多少不知道，但是内存使用降低不少。
（3）如果整数空间比较小，也就是说这10亿个数中有很多重复的数，最方便的办法估计就是维护一个HashTable对象ht，key就是整数值，value就是该整数值出现的次数。遍历这10亿个元素，得到ht后再对这个ht求第k大元素。那么这个算法的时间复杂度就是O(n)，n=10^10，空间复杂度是O(m)，m为整数空间大小。
（4）随机采样（或者将原来的顺序打乱，然后再顺序采样）。对样本中的整数进行出现次数的统计，这个时候采用HashTable的办法最好，时间复杂度是O(n)。如果对使用的空间有所限制，那么只能对该样本进行排序，再对排序后的样本进行100次遍历得到出现次数最多的前100个整数，则时间复杂度是O(nlogn)，空间复杂度是O(1)。
（5）好像有两种算法。假设要求数组a[1...n]中第k大元素。
（a）递归快排算法。若n<44（经验值）则直接排序返回第k大元素，否则，将1到n分成n/5个组，每个组5个元素，然后求这n/5个组的每组的中项元素，再求这n/5个中项元素的中项元素mm（注意，这里也可以用递归调用自身的方法）。然后对数组a根据mm分成三组，a1中的所有元素小于mm，a2中的所有元素等于mm，a3中的所有元素大于mm，如果|a1|>=k，则第k大元素在a1中，如果|a1|+|a2|>=k|a1|,则第k大元素就是mm，如果k>|a1|+|a2|，则第k大元素在a3中，再继续递归调用。这个算法的时间复杂度是O(n)。（注意，这里的中项mm也可以随机选择a中的元素，其时间复杂度也近似于O(n)，而且系数也比较小）。
（b）基于位查找（仅对于无符号整数的查找）。将32位整数的二进制位分为4段，每段8位，先比较a中所有元素高8位，找出第k大元素高8位的范围，再对应这高8位的范围在次高八位中找第k大元素的范围，...这样4次之后就可以找到第k大元素的。可以举个例子便于理解，在10个3位整数中找第k大元素，将3位分成3段，每段1位，每位之可能是0，1。如果这10个数的最高位0的个数m大于等于k，则第k大元素的最高位为0，再在最高位为0的元素中找次高位为第k大元素；如果10个数中最高位0的个数m大于k，则在最高位为1的元素中找此高位为第m-k大元素。...
（6）这个问题是前面那个问题的特例。有没有特殊的解法使效率又提高一些呢？我觉得没有，因为1和100本来就是常数级，和n比它们的差别是忽略不计的。
（7）简单的解法是对这个数组排序，然后再对排好序的数组进行一次遍历就可得到两两绝对值最差的最小值，时间复杂度是O(nlogn)。网上说求a的min，max和长度n，如果Dmax = (max-min+1)/n = 0，那么就说明数组a中有重复的元素，直接返回0。但是如果Dmax = (max-min+1)/n > 0,那么就以Dmax为箱的长度装入a的元素，再在箱内和箱间比较。我不懂为什么，但是这个空间复杂度是O(max)，而且好像如果a是1, 2, 3...100，那么Dmax就是1了，那么a不是没有动吗？还有人说够找数组b，b[i] = a[i] - a[i+1]，则a[i]-a[j]=b[i]+b[i+1]+...+b[j-1]也不知下文了，看来这个题比较搞啊。就是奥赛题，BS。