目录
题目描述
思路分析
我的题解
题目描述
给你两个正整数 n 和 k 。如果正整数 i 满足 n % i == 0 ,那么我们就说正整数 i 是整数 n 的因子。考虑整数 n 的所有因子,将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ,请你返回 -1 。
示例 1:
输入:n = 12, k = 3
输出:3
解释:因子列表包括 [1, 2, 3, 4, 6, 12],第 3 个因子是 3 。
示例 2:输入:n = 7, k = 2
输出:7
解释:因子列表包括 [1, 7] ,第 2 个因子是 7 。
示例 3:输入:n = 4, k = 4
输出:-1
解释:因子列表包括 [1, 2, 4] ,只有 3 个因子,所以我们应该返回 -1 。
提示:
1 <= k <= n <= 1000
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/the-kth-factor-of-n
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路分析
这题最容易想到的就是把n的因数都枚举一遍,然后再查找第k个元素,这种做法的时间复杂度是O(n)的,但很显然我们还有更好的解法。
我们设x*y=n,假设x从1开始递增,那么y就被动的从n开始递减。所以我们就没有必要把n的因数都枚举一遍,只需要枚举到√n就足够了,因为当x=y=√n时,等式成立。所以我们就完全可以根据x从1到√n之间所有n的整因数来推出另一半的内容。
我们把所有的因数排序过后的内容想象成一个数组,此时x的范围就是1到n,那么x从1到√n范围对应的数组就是相当于将原数组减半。此时我们将这个减半的数组命名为HalfFactor,并未减半数组(即枚举1到n所有因数的数组)长度为m,那么对k和m进行判断,如果k<=(m+1)/2,就说明我们要找的数刚好就在我们我们减半之后的数组HalfFactor中,那么就可以直接根据下标返回HalfFactor[k],如果k>(m+1)/2就说明我们要找的数是不在HalfFactor数组中的,这时就需要推出来一个规律性的东西,因为x*y=n,所以此时n除以对应下标的元素就是我们想要的那个因数。以12的因数为例 [1, 2, 3, 4, 6, 12] ,我们发现它们是对称的,所以我们不难推出:当k>(m+1)/2时,返回的是n/HalfFactor(m+1-k)。
时间复杂度:O(√n)
我的题解
class Solution {
public:
int kthFactor(int n, int k)
{
vector<int> HalfFactor = {0};
for(int a = 1; a*a <= n;a++)
{
if (n % a == 0)
HalfFactor.push_back(a);
}
int x = HalfFactor.size() - 1;
int m = HalfFactor[x]*HalfFactor[x] == n ? x*2-1 : x*2;
if(k <= (m+1)/2)
return HalfFactor[k];
else if(k > (m+1)/2 && k < m+1)
return n / HalfFactor[m+1-k];
return -1;
}
};