扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
题目:
**给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例：
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]**
看题目条件给的数据大小我就想用计数排序,但是怎么不申请额外空间呢?
其实完全可以利用每个元素的高位数据保存信息. 但是要确定要保存的信息的范围大小
比如你保存的是1-100 那你得给高8位留下来保存数据 底24位用来保存这个位置真实的数据值
leetcode上跑了还不错
int* findDuplicates(int* nums, int numsSize, int* returnSize)
{
//把每个元素的高16位和低16位分别保存2个信息点就可以了
for (int m=0;m> 16; //当前的数字 //取下高16位
int g16 = high26; //如果不是空
g16++;
nums[realvalue -1] = (nums[realvalue - 1]&65535) | (g16<<16);
}
//申请额外空间保存返回结果这个应该不算额外空间吧
int *result = malloc(sizeof(int)*numsSize);
int cc = 0;
for (int m = 0; m < numsSize; m++)
{
int high26 = (nums[m]>>16);
if (2 == high26)
{
result[cc++] = m + 1;
}
// printf("%d 出现%d次\n", m + 1, high26);
}
*returnSize = cc;
return result;
} 时间
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网