我有一个unsorted整数的列表,我想找到那些有重复项的元素。
val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)
字符串
我可以用dup.distinct找到集合中的不同元素,所以我把答案写如下。
val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)
val distinct = dup.distinct
val elementsWithCounts = distinct.map( (a:Int) => (a, dup.count( (b:Int) => a == b )) )
val duplicatesRemoved = elementsWithCounts.filter( (pair: Pair[Int,Int]) => { pair._2 <= 1 } )
val withDuplicates = elementsWithCounts.filter( (pair: Pair[Int,Int]) => { pair._2 > 1 } )
型
有没有更简单的办法解决这个问题?
7条答案
按热度按时间00jrzges1#
试试这个:
字符串
groupBy
将每个不同的整数与其出现的列表相关联。collect
基本上是map
,其中忽略不匹配的元素。case
后面的匹配模式将匹配与符合模式List(_,_,_*)
的列表相关联的整数x
,该列表至少有两个元素,每个元素由下划线表示,因为我们实际上不需要存储这些值(并且这两个元素后面可以是零个或更多个元素:_*
)的数据。您还可以:
型
它比您提供的方法快得多,因为它不必重复传递数据。
kiayqfof2#
有点晚了,但这里有另一种方法:
字符串
diff
给出了参数(dup.distinct
)中的所有额外项,这些项是重复项。kmpatx3s3#
另一种方法是使用
foldLeft
,并采用困难的方式。我们从两个空集开始。一个是我们至少见过一次的元素。另一个是我们至少见过两次的元素(也称为重复)。
我们遍历列表。当当前元素已经被看到(
seen(cur)
)时,它是一个副本,因此被添加到duplicates
。否则,我们将其添加到seen
。结果现在是包含重复项的第二个集合。我们也可以把它写成一个泛型方法。
字符串
ktecyv1j4#
**总结:**我写了一个非常有效的函数,它返回
List.distinct
和List
,List
由每个出现一次以上的元素和元素重复出现的索引组成。**详细信息:**如果您需要更多关于重复本身的信息,就像我一样,我已经编写了一个更通用的函数,它在
List
上迭代一次(因为顺序很重要),并返回一个Tuple2
,其中包含删除的原始List
(删除第一个之后的所有重复;即与调用distinct
相同)和第二List
,第二List
示出了每个副本和它在原始List
内出现的Int
索引。我已经基于general performance characteristics of the Scala collections实现了两次函数;
filterDupesL
(其中L表示线性)和filterDupesEc
(其中Ec表示有效常数)。下面是“线性”函数:
字符串
下面是一个例子,可能会让它更直观一点。给定此String值列表:
型
...然后执行以下操作:
型
结果是:
型
如果你只想要副本,你只需要
map
跨dupeAndIndexes
调用distinct
:型
...或全部在一个呼叫中:
型
...或者如果首选
Set
,则跳过distinct
并调用toSet
...型
...或全部在一个呼叫中:
型
对于非常大的
List
s,考虑使用这个更高效的版本(它使用额外的Set
来在有效的恒定时间内更改contains
检查):下面是“有效常量”函数:
型
以上两个函数都是我的开源Scala库ScalaOlio中的
filterDupes
函数的改编。它位于org.scalaolio.collection.immutable.List_._
。34gzjxbg5#
字符串
我们首先将每个元素与
false
(Map阶段)相关联,一旦发现重复,我们就将其与true
(缩减阶段)相关联。我们利用这样一个事实,即对于每个元素,只有当该元素是重复的时,才执行reduce阶段。然后,我们过滤,只保留与true
相关联的元素(过滤阶段)。这适用于trait
Seq
的所有实现。时间和空间复杂度均为
O(n)
。与其他答案比较:
1.@dhg answer不适用于所有类型的序列。例如,它适用于
List
,但会对Array
产生不正确的结果(因为List
模式匹配不会对Array
起作用)。此外,尽管它具有相同的时间和空间复杂度,但它为每个元素创建了一个List
,其中包含相应元素的所有副本,只是为了检查列表是否有多个元素。这意味着内存占用和运行时间会更高。1.@Luigi Plinge的回答很好,很优雅。但是,它创建了一个类似于散列表的中间数据结构3次(
diff
为1次,distinct
为2次),因此运行时间可能更高。yhxst69z6#
我要加入一个班轮派对。
不如这样:
字符串
bfhwhh0e7#
我最喜欢的是
字符串