Find the First K Missing Positive Numbers

vector<int> firstKMissing(vector<int> nums, int k) {
    int n = nums.size();
    for (int i = 0; i < n; ) {
        if (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) swap(nums[i], nums[nums[i] - 1]);
        else ++i;
    }
    vector<int> out;
    unordered_set<int> displaced;
    for (int i = 0; i < n && (int)out.size() < k; ++i) {
        if (nums[i] != i + 1) {
            out.push_back(i + 1);
            displaced.insert(nums[i]);
        }
    }
    int extra = n + 1;
    while ((int)out.size() < k) {
        if (!displaced.count(extra)) out.push_back(extra);
        ++extra;
    }
    return out;
}

func firstKMissing(nums []int, k int) []int {
    n := len(nums)
    for i := 0; i < n; {
        if nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        } else {
            i++
        }
    }
    out := make([]int, 0, k)
    displaced := map[int]bool{}
    for i := 0; i < n && len(out) < k; i++ {
        if nums[i] != i+1 {
            out = append(out, i+1)
            displaced[nums[i]] = true
        }
    }
    extra := n + 1
    for len(out) < k {
        if !displaced[extra] {
            out = append(out, extra)
        }
        extra++
    }
    return out
}

from typing import List

class Solution:
    def firstKMissing(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        i = 0
        while i < n:
            if 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
            else:
                i += 1
        out: List[int] = []
        displaced: set = set()
        for i in range(n):
            if len(out) >= k:
                break
            if nums[i] != i + 1:
                out.append(i + 1)
                displaced.add(nums[i])
        extra = n + 1
        while len(out) < k:
            if extra not in displaced:
                out.append(extra)
            extra += 1
        return out

var firstKMissing = function(nums, k) {
    const n = nums.length;
    let i = 0;
    while (i < n) {
        if (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            const j = nums[i] - 1;
            [nums[i], nums[j]] = [nums[j], nums[i]];
        } else {
            i++;
        }
    }
    const out = [];
    const displaced = new Set();
    for (let i = 0; i < n && out.length < k; i++) {
        if (nums[i] !== i + 1) {
            out.push(i + 1);
            displaced.add(nums[i]);
        }
    }
    let extra = n + 1;
    while (out.length < k) {
        if (!displaced.has(extra)) out.push(extra);
        extra++;
    }
    return out;
};

class Solution {
    public List<Integer> firstKMissing(int[] nums, int k) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            if (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int j = nums[i] - 1;
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            } else {
                i++;
            }
        }
        List<Integer> out = new ArrayList<>();
        Set<Integer> displaced = new HashSet<>();
        for (int idx = 0; idx < n && out.size() < k; idx++) {
            if (nums[idx] != idx + 1) {
                out.add(idx + 1);
                displaced.add(nums[idx]);
            }
        }
        int extra = n + 1;
        while (out.size() < k) {
            if (!displaced.contains(extra)) out.add(extra);
            extra++;
        }
        return out;
    }
}

function firstKMissing(nums: number[], k: number): number[] {
    const n = nums.length;
    let i = 0;
    while (i < n) {
        if (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            const j = nums[i] - 1;
            [nums[i], nums[j]] = [nums[j], nums[i]];
        } else {
            i++;
        }
    }
    const out: number[] = [];
    const displaced = new Set<number>();
    for (let idx = 0; idx < n && out.length < k; idx++) {
        if (nums[idx] !== idx + 1) {
            out.push(idx + 1);
            displaced.add(nums[idx]);
        }
    }
    let extra = n + 1;
    while (out.length < k) {
        if (!displaced.has(extra)) out.push(extra);
        extra++;
    }
    return out;
}