Given two positive integers n and k.
A factor of an integer n is defined as an integer i where n % i == 0.
Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.
Example 1:
Input: n = 12, k = 3 Output: 3 Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Example 2:
Input: n = 7, k = 2 Output: 7 Explanation: Factors list is [1, 7], the 2nd factor is 7.
Example 3:
Input: n = 4, k = 4 Output: -1 Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.
Example 4:
Input: n = 1, k = 1 Output: 1 Explanation: Factors list is [1], the 1st factor is 1.
Example 5:
Input: n = 1000, k = 3 Output: 4 Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].
Constraints:
1 <= k <= n <= 1000
N的第K个因子。
题意是给两个正整数 N 和 K，请找到从小到大的第K个N的因子，如果N的因子不足K个，返回 -1。
这是一道数学题，我这里提供两种办法，介于数据量不是非常大，其实运行速度看不出区别。
第一种办法就是从1到N不断地找一个除数去跟N做除法，如果这个数字可以被N整除，则count++，当count == K的时候，则可以break了，返回那个除数。如果遍历完N之后count大于0，则说明N的因子不足K个，返回-1。
时间O(n)
空间O(1)
Java实现
1 class Solution {
2 public int kthFactor(int n, int k) {
3 int res = -1;
4 // corner case
5 if (k > n) {
6 return res;
7 }
8
9 // normal case
10 int count = k;
11 for (int i = 1; i <= n; i++) {
12 if (n % i == 0) {
13 count--;
14 res = i;
15 }
16 if (count == 0) {
17 break;
18 }
19 }
20 return count == 0 ? res : -1;
21 }
22 }
第二种办法也类似。注意对于每一个N的因子 i ，如果N能被 i 整除，那么一定会产生一个商 N / i 。我们在遍历的时候，可以只遍历到N的平方根，然后建立一个list来存储商 N / i 。我们从1开始扫描到 sqrt(N) ，如果i * i 不等于N则把n / i 加入list。这里相当于是用for循环记录N的一半因子，用list去记录N的另一半因子。当count == k的时候，则说明找到了第K个因子，我们就返回这个因子。如果第K个因子不在count这一边，那么就一定在list中，注意list里面的数字是从大到小存储的所以注意最后从list中拿数字的方法。
时间O(sqrt(N))
空间O(n) - list
Java实现
1 class Solution {
2 public int kthFactor(int n, int k) {
3 List<Integer> list = new ArrayList<>();
4 int count = 0;
5 for (int i = 1; i * i <= n; i++) {
6 if (n % i == 0) {
7 if (i * i != n) {
8 list.add(n / i);
9 }
10 count++;
11 if (count == k) {
12 return i;
13 }
14 }
15 }
16 if (list.size() + count < k) {
17 return -1;
18 }
19 return list.get(list.size() - (k - count));
20 }
21 }