本篇博客会讲解力扣“1920. 基于排列构建数组”的解题思路,这是题目链接。
先来审下题:
以下是输出示例:
以下是提示:
相信读完题的你已经感到没啥意思了,感觉做这道题就是在浪费时间。但是还是建议你看下去,接下来会有一个很有意思的思路。在讲解这个有意思的思路之前,先按照正常的思路实现一下:
int* buildArray(int* nums, int numsSize, int* returnSize) {
int* ret = (int*)malloc(sizeof(int) * numsSize);
*returnSize = numsSize;
// 根据指定规则,构建数组
for (int i = 0; i < numsSize; ++i)
{
ret[i] = nums[nums[i]];
}
return ret;
}
这样就过了。事实上,我更推荐这个正常的思路。不过这个思路开辟了一个新的数组,有没有什么手段,直接在原数组上操作呢?
你可能会问:怎么可能?难道我们要同时在一个数组中存储原数据和结果数据?
答案是:是的!类比一下:假设我们要存储的数据是10以内的,那么用一个十进制数就能够存的下了。比如:37就代表了2个数,一个是37%10=7,另一个是37/10=3。
而本题中的数据是1000以内的,所以可以用“1000进制”来存储。我们规定一个数n,n%1000代表原数据,而n/1000代表结果数据。那么我们就可以遍历数组,对nums[i]做如下操作:
nums[i] += 1000 * (nums[nums[i]] % 1000);
在nums[i]操作之前,nums[i]的值就是它本身,可以使用nums[nums[i]]找到其中的原数据,但是还要%1000
。找到该数据后,还要存储到nums[i]中,就*1000
再加到nums[i]上即可。实际拿出结果数据,只需要/1000
。
具体实现的代码如下:
int* buildArray(int* nums, int numsSize, int* returnSize){
// nums[i]<1000,故采取1000进制
// nums[i]%1000为原来数据
// nums[i]/1000为结果数据
for (int i = 0; i < numsSize; ++i)
{
nums[i] += 1000 * (nums[nums[i]] % 1000);
}
// 取出结果数据
for (int i = 0; i < numsSize; ++i)
{
nums[i] /= 1000;
}
*returnSize = numsSize;
return nums;
}
这样也能过。文章来源:https://www.toymoban.com/news/detail-441488.html
总结
- 常规思路没什么好说的。
- 如果我们想把两个1000以内的数存储到一块空间中,可以使用1000进制。
感谢大家的阅读!文章来源地址https://www.toymoban.com/news/detail-441488.html
到了这里,关于从10进制到1000进制:一场数字的盛宴的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!