【数据结构和算法】从 1 - n 的连续整数中随机去掉 2 个,剩下的数字打乱顺序放到整型数组中,找出去掉的数字?
2021/4/27 14:27:20
本文主要是介绍【数据结构和算法】从 1 - n 的连续整数中随机去掉 2 个,剩下的数字打乱顺序放到整型数组中,找出去掉的数字?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题描述:从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 个,剩下的数字打乱顺序放到整型数组中,找出去掉的数字?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南