import java.util.*;
class FirstKMissingPositive {
public static List findNumbers(int[] nums, int k) {
List missingNumbers = new ArrayList<>();
// TODO: Write your code here
int i = 0;
while (i < nums.length)
{
int num = nums[i];
if (num == i+1 || num <= 0 || num > nums.length || num == nums[num-1])
{
i++;
}
else
{
swap(nums, i, num-1);
}
}
Queue<Integer> minHeap = new PriorityQueue<>();
for (i=0; i<nums.length; i++)
{
if (nums[i] != i+1 && k > 0)
{
missingNumbers.add(i+1);
k--;
minHeap.add(nums[i]);
}
}
int nextNum = nums.length + 1;
while (k > 0)
{
if (!minHeap.isEmpty() && minHeap.peek() == nextNum)
{
minHeap.poll();
nextNum++;
}
else
{
missingNumbers.add(nextNum++);
k--;
}
}
return missingNumbers;
}
private static void swap(int[] nums, int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}