新华三笔试题 - 求最中间的因数

本文最后更新于:2020年9月25日 晚上

题目

时间限制: C/C++1秒,其他语言2秒

空间限制: C/C++ 262144K,其他语言 524288K

64bit IO Format: %lld

请完成最中间因数函数 MidFactor,寻找一个整数的所有因数中最中间的那个数。

举例:

  • 16有5个因数,分别是1,2,4,8,16,最中间的是4
  • 12有6个因数,分别是1,2,3,4,6,12.最中间的是3
long long MidFactor(long long llVal)
{
}

int main (int argc, char *argvD)
{
    long long llVal =0;
    if (argc < 2)
    {
        return 1;
    }
    llVal= (long long)atol(argv[1);
    printf("%ll", MidFactor(llVal);
    return 0;
}

[]$ ./a.out 16
4

[]$ ./a.out 12
3

示例1

输入

16

输出

4

解题思路

这个题做得挺快的,暴力解的话遍历就可以,主要需要注意遍历的边界。

首先,要找到一个数的所有因数,一下就能想到的就是从 1 开始遍历,能整除的就是其因数,代码大概是这样:

for (int i = 1; i < num; i++){
    if(num % i) {
        // i是num的因数
    }
}

然后进一步的不难发现,任意的一个因数 i 都和 num / i 对应是一组因数,也就是说上面的 if 语句内部得到了因数 i 的同时还得到了另一个与之对应的因数 num / i

再回到这个题里面来,这种要找中间的值的问题,往往我们会考虑把所有可能的值找出来后,再去找位于中间的那一个。但正如前面所说,因数总是一一对应的,这就意味着我们从 1 开始遍历,i 变大的同时,与之对应的 num / i 在逐渐变小,以 16 为例:

1 - 16
2 - 8
4 - 4  // 最中间的因数
8 - 2
16 - 1

i 逐渐增大,会在过了某个临界值(如上4)之后大于 num / i ,而这个临界值其实就是最中间的因数。

因此,只需要把遍历的边界设置为 i 从 1 开始且 i * i <= num 即可,初始化最中间的因数 mid 为 1 ,每新找到一个更大的因数就更新 mid 的值,当 i 越过边界跳出循环后,mid 的值即为 num 所有因数中最中间的哪一个。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 求 一个数    最中间的因素
     * @param llVal long长整型 正整数
     * @return long长整型
     */
    long long MidFactor(long long llVal) {
        // write code here
        long long mid = 1;
        for (long long i = 1; i * i <= llVal; i++) {
            if (llVal % i == 0) {
                mid = i;
            }
        }
        return mid;
    }
};

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!