《算法零基础100讲》(第10讲) 因子分解和枚举（C语言题解）

• 1492. n 的第 k 个因子
• 1362.最接近的因数

说句实话，这道题好水呀，这种难度的题也被放在中等难度。
直接遍历，时间复杂度为O(n)，遍历区间为[1，n]，如果n % i == 0，k–，直到k==0，返回i，如果遍历结束，还未找到第k个因子，return -1。
直接上代码：

int kthFactor(int n, int k){
    for(int i = 1; i <= n; i++){
		//判断是否为因子
        if(n % i == 0){
            k--;
            if(k == 0){
                return i;
            }
        }
    }
    //若到达这里说明n所拥有的因子数量小于k
    return -1;
}

这道题主要针对那两个条件进行分析：

1. 首先两个数的乘积要等与num + 1或num + 2
2. 其次就是两个数的差的绝对值要最小

很显然，我们所要做的就是找出num+1，num + 2的因子组，并找出其中最接近的一组。
代码如下：

int* closestDivisors(int num, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2; 
    int sub = INT_MAX;//将sub初始化为无穷大
    //遍历num+1，和num+2的因子
    for(int i = num + 1; i <= num + 2; i++){
		
        for(int j = 1; j * j <= i; j++){
        	//如果j不是i的因子结束本次循环
            if(i % j){
                continue;
            }
            //判断sub的值大于新的因子组的差的绝对值
            if(sub > abs(i / j - j)){
                sub = abs(i / j - j);
                ret[0] = j;
                ret[1] = i / j;
            }
        }
    }
    return ret;
}

第三道有点难，先划着水来^ _ ^