集合的偏移量和限制

Question

我有两组有序的 Integers - SortedSet<Integer>，称它们为 set1 和 set2。我需要找到该集合的并集和 return 子集偏移量 10 限制 10。我是什么意思？

Set1:
1,2,5,6,7,8,11,21,23,543,1002

Set2:
11,12,15,16,17,8,111,121,123,1543,11002

Union:
1,2,5,6,7,8,11,21,23,543,1002,12,15,16,17,111,121,123,1543,11002

Union offset 10 limit 10:
1002,12,15,16,17,111,121,123,1543,11002

请注意，联合中 8 和 11 的基数是 1。

我正在寻找一种算法，使我不会将整个集合加载到内存中（因为这些集合可能非常大，我不会浪费服务器的资源）。有没有办法做到这一点？也许一些像 commons 或 guava 这样的即时库可以帮助？

UPD: 我自己不使用 Java 8，但是使用它的解决方案也很有趣。

Answer 1

算法很简单。

Create empty hash
Create empty array
Set waste counter to 0
Iterate all sets (2 or more)
  Iterate set values
    If value not in hash
      Insert value into hash
      Increase waste counter
        If waste counter > offset (10)
          Insert value into array
          If array length == limit (10)
            Done - return array

Answer 2

@Amit 的回答很好，但如果偏移量也很大，内存效率仍然会有点低。这是另一种方法，

Have a pointer on each set,
while offset > 0:
    if setA pointer value < setB pointer value
        increment setA pointer
        decrement offset
    else
        increment setB pointer

add "limit" numbers starting from setA pointer to the output array.
if end of setA is reached before "limit" numbers are present,
    add the remaining numbers from setB pointer to the output array.

注意：这仅适用于排序集。
如果不清楚，请告诉我。

集合的偏移量和限制

Offset and limit for a set

java

algorithm

collections