【跟着英雄哥学算法第(10)讲】力扣1362.最接近的因子 [c语言]
前言
这是初学算法的我
这是加入万人学习社区的我

在此,博主准备分享一个万人学习的社区,这里有许多大佬指引前行,大家互相勉励学习,欢迎大家加入这个社区。博主也是小白,理解大家的困惑,一个人学习太艰难了,不容易走的很远。
万人千题社区 https://bbs.csdn.net/forums/hero?category=0
最接近的因子
力扣https://leetcode-cn.com/problems/closest-divisors/
一、分析
观察问题性质可知,对任意一个在 [sqrt(n), n] 范围内的因数,一定有一个与其对称的在 [1, sqrt( n)] 范围内的因数。因此,遍历因数只需要遍历 [1, sqrt( n)] 范围即可。
另外,当 [1, sqrt( n)] 范围内的因数最大时,与其对称的 [sqrt( n), n] 范围内的因数也最小,此时这两个数字之间的差值一定是所有可能性中最小的。因此,我们只需要找到 [1, sqrt (n)] 中的最大因数即可停止。例如 36的因子为1,2,3,4,6,9,12,18,36.
1~sqrt(n)的最大因数为6,对称后发现 sqrt(n)~ n的最小因子为6
二、代码实现
- int* closestDivisors(int num, int* returnSize) {
- int* ret = (int*)malloc(2 * sizeof(int)); // 给ret数组分配了2个字节的内存空间
- int n, i, sub = -1;
- for (n = num + 1; n <= num + 2; ++n) { //
- for (i = 1; i <=sqrt (n); ++i) {
- if (n %% i) //
- continue;
- if (sub == -1 || abs(n / i - i) < sub) { // ||的解释:当前者为假时后者才会进行判断
- sub = abs(n / i - i);
- ret[0] = n / i; // 赋值ret[0] ret[1]
- ret[1] = i;
- }
- }
- }
- *returnSize = 2; // 初始化数组长度为2
- return ret; // 返回ret数组
- }
补充
malloc函数
malloc()函数其实就在内存中找一片指定大小的空间,然后将这个空间的首地址范围给一个指针变量,这里的指针变量可以是一个单独的指针,也可以是一个数组的首地址,这要看malloc()函数中参数size的具体内容。
int* p;
p = (int *) malloc (sizeof(int)); //默认一个内存空间
int* p = (int *) malloc ( sizeof(int) * 100 ); //分配可以放得下100个整数的内存空间。char *p;
p=(char *)malloc(100);
注意:malloc 只管分配内存,并不能对所得的内存进行初始化,所以得到的一片新内存中,其值将是随机的。