百科问答小站 logo
百科问答小站 font logo



C#中关于List<T>和HashSet<T>应用的效率问题? 第1页

  

user avatar   oahzir 网友的相关建议: 
      

这是two sum那道题吧。

很明显用了hash table来储存数据,是为了用O(n)的space来换取O(n)的时间,也就是查找元素的时间是O(1)。

你这样用List,contains查找时间还是O(n)。

跟你直接写个for loop用brute force有什么区别呢?


user avatar   wizardforcel 网友的相关建议: 
      

如果拆开来看,List<T>里面是线序集,HashSet<T>里面是散列表。

与Dictionary<K,V>相比,List<T>可以看成下标到值的映射,HashSet<T>可以看成值自己到自己的映射。判断一个值是否存在,前者相当于是用值去找下标,要遍历一遍容器;后者相当于用映射前的值去找映射后的值,只需要计算出来值的hash,然后直接访问就好了。


user avatar   Ivony 网友的相关建议: 
      

简单说,一个时间复杂度O(1),一个时间复杂度O(n)。

而且HashSet无序不重,和List完全不同。


判断一个数组是否包含重复元素,其实只需要一个个添加到HashSet,然后检查Add方法的返回值就可以了:

       var set = new HashSet<int>(); foreach( var i in array )   if ( set.Add( i ) == false )     return true;  return false;      

当然不考虑效率的花式玩法很多,但都比一个个去Contains要性能好:

       return array.Length != array.Distinct().Count();      
       return array.GroupBy( i => i ).Any( g => g.Count() > 1 );     

user avatar   jeffz 网友的相关建议: 
      

先别刷题了,看下基础数据结构书。




  

相关话题

  我编程写代码被我妈一直说成玩电脑打游戏,我该咋办? 
  c#入门书籍有推荐吗? 
  C#中struct和class的使用区别是什么? 
  游戏开发在向去编程化发展吗? 
  为什么好多编程“牛人”不喜欢用 Microsoft Visual Studio? 
  为什么国内那么多公司乱用 C# 的三层架构? 
  人工智能(AI)时代,让孩子学编程还是学艺术? 
  C#填了java哪些坑?java填了C++哪些坑?C++填了C哪些坑? 
  将文件编译成某种代码,打印到A4纸上,这种想法是否可行? 
  XML在数据传输哪些方面会比JSON有优势,在哪些领域更加适合? 

前一个讨论
E9&"-"&E10&"-"&E11是啥意思?
下一个讨论
对富人征收更多税收的社会依据是什么?





© 2025-06-05 - tinynew.org. All Rights Reserved.
© 2025-06-05 - tinynew.org. 保留所有权利