Let k be yourCollection.length() * 0.1
and n = yourCollection.length()
.
Find the k-th smallest element (QuickSelect or Median of 5), where the key is your fitness. Let's call it p
. This can be done in O(n)
.
Then traverse through the collection and remove all the items with fitness less than p.fitness. We've got an O(n)
solution.
Or, you can create a heap in O(n)
with key=fitness
and remove k
elements from it in O(k * log(n))
.