Smallest K Integers O(n)

class Solution {
    int partition(vector<int> &nums, int left, int right) {
        int randomIndex = left + rand() % (right - left + 1);
        std::swap(nums[randomIndex], nums[right]);
        int value = nums[right];
        int correctIndex = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] <= value) {
                std::swap(nums[correctIndex++], nums[i]);
            }
        }
        return correctIndex - 1;
    }

    void smallestKNums(vector<int>& nums, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int pivot = partition(nums, left, right);
        if (pivot - left + 1 >= k) {
            smallestKNums(nums, left, pivot - 1, k);
        } else {
            smallestKNums(nums, pivot + 1, right, k - (pivot - left + 1));
        }
    }

public:
    vector<int> kSmallest(vector<int>& nums, int k) {
        const int n = nums.size();
        smallestKNums(nums, 0, n - 1, k);
        return vector<int>(nums.begin(), nums.begin() + k);
    }
};