WHCSRL 技术网

【跟着英雄哥学算法第(10)讲】力扣1362.最接近的因子 [c语言]

前言

          这是初学算法的我

 

          这是加入万人学习社区的我                  

 

       在此,博主准备分享一个万人学习的社区,这里有许多大佬指引前行,大家互相勉励学习,欢迎大家加入这个社区。博主也是小白,理解大家的困惑,一个人学习太艰难了,不容易走的很远。

        万人千题社区    https://bbs.csdn.net/forums/hero?category=0


 


最接近的因子

                 力扣icon-default.png?t=L9C2https://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,69,12,18,36.     

              1~sqrt(n)的最大因数为6,对称后发现 sqrt(n)~ n的最小因子为6   

 

二、代码实现

  1. int* closestDivisors(int num, int* returnSize) {
  2. int* ret = (int*)malloc(2 * sizeof(int)); // 给ret数组分配了2个字节的内存空间
  3. int n, i, sub = -1;
  4. for (n = num + 1; n <= num + 2; ++n) { //
  5. for (i = 1; i <=sqrt (n); ++i) {
  6. if (n %% i) //
  7. continue;
  8. if (sub == -1 || abs(n / i - i) < sub) { // ||的解释:当前者为假时后者才会进行判断
  9. sub = abs(n / i - i);
  10. ret[0] = n / i; // 赋值ret[0] ret[1]
  11. ret[1] = i;
  12. }
  13. }
  14. }
  15. *returnSize = 2; // 初始化数组长度为2
  16. return ret; // 返回ret数组
  17. }


补充

     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 只管分配内存,并不能对所得的内存进行初始化,所以得到的一片新内存中,其值将是随机的。

推荐阅读