【数据结构和算法】从 1 - n 的连续整数中随机去掉 2 个，剩下的数字打乱顺序放到整型数组中，找出去掉的数字？
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构和算法】从 1 - n 的连续整数中随机去掉 2 个，剩下的数字打乱顺序放到整型数组中，找出去掉的数字？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2494字，纯文字阅读大概需要4分钟。
内容图文
问题描述：从1到n共n个连续有序的数字,任意去掉2个,把剩下的(n-2)个打乱顺序放到了一个整形数组中,求出那两个去掉的数字？不能通过排序实现。
这道问题，如果用排序的话是非常简单的，先排序，然后遍历一遍，很容易就能找出去掉的数字，时间复杂度为O（nlogn）。
不过题目要求不能排序，所以另一个很容易想到的方法就是两层 for 循环嵌套，第一层循环遍历 1 - n，第二层循环遍历数组，也可以实现。不过时间复杂度有点高，是 O（n^2）。
通过学习，我找到了更加简单方便的方法。
首先我们将问题简化一下，如果只删除一个数字的情况，如何解决呢？
问题描述：从1到n共n个连续有序的数字,任意去掉 1 个,把剩下的 (n-1) 个打乱顺序放到了一个整形数组中,求出那两个去掉的数字？不能通过排序实现。
思路分析：
用 求和 的方式来解决，计算 1-n 的和，以及数组中（n-1）个数字的和，二者相差的数字，就是删掉的那个数字。
时间复杂度为 O（n）。
int findLost(int *a, int n)
{
int res = 0;
for(int i = 0; i < n; i++)
{
res = res + i + 1 - a[i];
}
return res;
}回到我们最初的问题，删除两个的话，如何判断呢？
用上述的方法，我们可以找出被删除的两个数的和，但是两个数具体是多少该怎么求呢？
问题描述：从1到n共n个连续有序的数字,任意去掉2个,把剩下的(n-2)个打乱顺序放到了一个整形数组中,求出那两个去掉的数字？不能通过排序实现。
思路分析：
用 1 + 2 + ... + n，减去数组中的数字，可以得到被删除的两个数字之和，即 a + b。
同理，我们可以用 1 * 2 * ... * n 的积，除以数组中的数字，即可得到被删除的两个数字之积，即 a * b。
而根据 （a - b)^2 = (a + b)^2 - 4ab，可以推导出 a 和 b 的值。
void findLost(int *a, int n)
{
int res1 = 0;
int res2 = 1;
for(int i = 0; i < n; i++)
{
res1 = res1 + i + 1 - a[i];
res2 = res * (i+1) / a[i];
}
int a = (sqrt(res1*res1 - 4*res2) + res1) / 2;
int b = res1 - a;
cout<< a << " " << b;
}如果我们将问题再变换一下，如果是随机删除一个数字，然后再将剩余数字中任取一个重复一次，组成 n 个数字的数字，如何找出删除的数字和重复的数字。
问题描述：从1到n共n个连续有序的数字,随机取一个去掉，再在剩余的数字中随机取一个重复,把得到的 n 个数字打乱顺序放到了一个整形数组中,找出去掉的数字和重复的数字？不能通过排序实现。
思路分析：
整体思路还是跟上面的一致（假设删除的是数字是 a ，重复的数字是 b）。
计算 1 + 2 + ... + n，减去数组中的数字，得到的结果是 a - b。
同理，我们计算 1 * 2 * ... * n 的积，除以数组中的数字，得到的结果是 a / b。
因为，
所以 ，
void findLost(int *a, int n)
{
int res1 = 0;
int res2 = 1;
for(int i = 0; i < n; i++)
{
res1 = res1 + i + 1 - a[i];
res2 = res * (i+1) / a[i];
}
int b = res1 / (res2 - 1);
int a = res1 + b;
cout<< a << " " << b;
}
内容总结
以上是互联网集市为您收集整理的【数据结构和算法】从 1 - n 的连续整数中随机去掉 2 个，剩下的数字打乱顺序放到整型数组中，找出去掉的数字？全部内容，希望文章能够帮你解决【数据结构和算法】从 1 - n 的连续整数中随机去掉 2 个，剩下的数字打乱顺序放到整型数组中，找出去掉的数字？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。