The kth Factor of n Solutions in C++

/// Source : https://leetcode.com/problems/the-kth-factor-of-n/
/// Author : liuyubobobo
/// Time   : 2020-06-27

#include <iostream>
#include <vector>

using namespace std;


/// Brute Force
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int kthFactor(int n, int k) {

        vector<int> factors;
        for(int i = 1; i <= n; i ++)
            if(n % i == 0) factors.push_back(i);
        return k - 1 < factors.size() ? factors[k - 1] : -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/the-kth-factor-of-n/
/// Author : liuyubobobo
/// Time   : 2020-06-27

#include <iostream>
#include <vector>

using namespace std;


/// Just calculate all the factors once
/// Time Complexity: O(sqrt(n))
/// Space Complexity: O(n)
class Solution {
public:
    int kthFactor(int n, int k) {

        vector<int> factors;
        for(int i = 1; i * i <= n; i ++) // 使用 i * i <= n，避免 sqrt(n) 运算的性能和精度问题
            if(n % i == 0){
                factors.push_back(i);

                // 对于 i * i == n 的情况要进行以下判断，
                // 如果 i * i == n，则 i 和 n / i 是一个数字，不能重复添加进 factors
                if(i * i != n)
                    factors.push_back(n / i);
            }
        sort(factors.begin(), factors.end());
        return k - 1 < factors.size() ? factors[k - 1] : -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/the-kth-factor-of-n/
/// Author : liuyubobobo
/// Time   : 2020-06-27

#include <iostream>
#include <vector>

using namespace std;


/// Just calculate all the factors once
/// Time Complexity: O(sqrt(n))
/// Space Complexity: O(n)
class Solution {
public:
    int kthFactor(int n, int k) {

        vector<int> factors;
        for(int i = 1; i * i <= n; i ++)
            if(n % i == 0){
                k --;
                if(!k) return i;
                if(i * i != n) factors.push_back(n / i);
            }
        return k - 1 < factors.size() ? factors[factors.size() - k] : -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/the-kth-factor-of-n/
/// Author : liuyubobobo
/// Time   : 2020-06-27

#include <iostream>
#include <vector>

using namespace std;


/// Just calculate all the factors once
/// Time Complexity: O(sqrt(n))
/// Space Complexity: O(1)
class Solution {
public:
    int kthFactor(int n, int k) {

        int i;
        for(i = 1; i * i <= n; i ++)
            if(n % i == 0){
                k --;
                if(!k) return i;
            }

        i--;
        for(i = (i * i == n ? i - 1 : i); i > 0; i --)
            if(n % i == 0){
                k --;
                if(!k) return n / i;
            }

        return -1;
    }
};


int main() {

    cout << Solution().kthFactor(4, 4) << endl;

    return 0;
}