前言
原文章出處專欄為： 演算法零基礎100講
若你也想學好演算法與資料結構，請跟著他的腳步: 英雄哪里出來
目錄
- 前言
- LeetCode 1492. n的第k個因子
- 分析
- 代碼
- LeetCode 1362. 最接近的因數
- 分析
- 代碼
LeetCode 1492. n的第k個因子
原題鏈接： 1492. n的第k個因子
分析
題目中說到，考慮整數n的所有因子，并升序排列，找出第k個，其實不用想的那么麻煩，
直接采用從1開始列舉，如果列舉的數字能整除 n ，則記錄一次，這樣列舉本來就是升序排列找到第K個，
代碼
int kthFactor(int n, int k)
{
int count = 0, ans = -1;
for (int i = 1; i <= n; ++i)
{
if (n % i == 0) //是因子記錄一次
count++;
if (count == k) //當記錄次數等于k,就找到了
{
ans = i;
break;
}
}
return ans;
}
LeetCode 1362. 最接近的因數
原題鏈接: 1362. 最接近的因數
分析
根據題意，首先要列舉num+1和num+2；
再從1到sqrt(num + 1)，1到sqrt(num+2)列舉，因為如果在1到sqrt(num+1)之間有因子，那么在sqrt(num+1)到（num+1)之間有對應的因子，
如果是因子的話，將兩個因子差的絕對值和上一次的因子作比較，如果差值更小，就將兩個因子放入該回傳的陣列中，
代碼
int* closestDivisors(int num, int* returnSize)
{
//申請回傳陣列
*returnSize = 2;
int* ans = (int*)malloc(sizeof(int) * 2);
if (NULL == ans) return NULL;
//先將第一次的差置為最大值，為了下面的比較
ans[0] = 0, ans[1] = INT_MAX;
//列舉 num+1 和 num+2
for (int n = num + 1; n <= num + 2; ++n)
{
for (int i = 1; i * i <= n; ++i)
{
if (n % i == 0) //如果是因子，就進來判斷
{
// 每次和上一次的差值作比較，更小的放入陣列
if (abs(n / i - i) < abs(ans[0] - ans[1]))
{
ans[0] = n / i;
ans[1] = i;
}
}
}
}
return ans;
}
由于我的理解能力和數學不太好，做到這一步也算可以，
謝謝大家觀看~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342125.html
標籤：其他