c++ - 使用 O(n) 时间和 O(1) 空间从数组中查找缺失的数字

标签 c++ algorithm time-complexity space-complexity

<分区>

我们有一个从 1 到 100 的数字数组。缺少两个数字。使用 O(n) 时间和 O(1) 空间找到这两个数字。请注意,数组中的那些数字未排序。 例子 : 假设有一个数组 [4, missing, 1, missing, 2] 可以看到,缺少的是3和5。假设从1到5的数字数组和两个数字都丢失了。实际上,它是 [4, 1, 2] 没有 3 和 5。

所以,我不知道如何解决这个问题。你们有人可以帮助我吗?我的编程语言是 C++。这是数组:

{24, 44, 19, 92, 1, 18, 28, 50, 88, 5, 52, 11, 76, 39, 82, 85, 65, 93, 98, 4, 72, 94, 45, 59, 48, 46, 47, 67, 87, 99, 14, 70, 80, 25, 20, 22, 21, 41, 77, 73, 2, 13, 36, 6, 27, 81, 29, 62, 8, 35, 32, 49, 10, 100, 90, 78, 30, 34, 51, 9, 43, 58, 26, 33, 64, 15, 17, 57, 12, 56, 61, 79, 75, 97, 84, 42, 55, 83, 91, 86, 38, 89, 96, 74, 23, 7, 68, 60, 16, 66, 69, 53, 3, 71, 37, 63, 54, 95}

最佳答案

对数组进行排序,遍历数组字段,与计数器 i 进行比较,如果 i 与字段 push_back( i) 在 vector 中。

关于c++ - 使用 O(n) 时间和 O(1) 空间从数组中查找缺失的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18046425/

相关文章:

arrays - 通过删除最小数量的元素,将给定的整数数组转换为排序数组

python - 变长队列BFS算法复杂度分析

c# - C# 中 foreach() 的复杂性。网

c++ - 在 VS 2012 项目中使用 libpq (PostgreSQL) 库

.net - 从 LPCWSTR 转换为 LPCSTR

c++ - Directx网格顶点问题

algorithm - 查找不包括某些对的连续子数组的数量

algorithm - 快速检查集合是否是存储集合的超集

arrays - 仅需 9 次比较即可在 8 个数字的数组中找到最小和第二小的数字

c++ - 与 ‘operator>>’ 不匹配(操作数类型为 ‘QDataStream’ 和 ‘QJsonObject’ )