在O(n)中的数组中查找重复项，并在C ++中使用O(1)多余的空间
假设我们有一个从0到n-1的数字列表。一个数字可以重复尽可能多的次数。我们必须找到重复的数字而不占用任何额外的空间。如果n = 7，则list类似于[5，2，3，5，1，6，6，2，3，4，5]。答案将是5、2、3。
为了解决这个问题，我们必须遵循以下步骤-
- list-paddingleft-2">
对于列表中的每个元素e，执行以下步骤-
符号：= A [e的绝对值]
如果符号为正，则使其为负
否则，这是重复。
示例
#include<iostream>
#include<cmath>
using namespace std;
void findDuplicates(int arr[], int size) {
for (int i = 0; i < size; i++) {
if (arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] *= -1;
else
cout << abs(arr[i]) << " ";
}
}
int main() {
int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};
int n = sizeof(arr)/sizeof(arr[0]);
findDuplicates(arr, n);
}
输出结果
5 2 3 1
-
本文向大家介绍在C ++中对O(1)额外空间中数组中所有元素的频率和O(n)时间进行计数，包括了在C ++中对O(1)额外空间中数组中所有元素的频率和O(n)时间进行计数的使用技巧和注意事项，需要的朋友参考一下 给定一个范围从值1到n的元素数组。有些元素是重复的，而有些则缺失。目的是找到O(n)时间和O(1)额外空间中所有元素的频率。 输入值 输出结果 说明-最高元素是5，输出显示每个元素出现在数
-
给定一个二叉树，我想返回最大和子树的根。 最大子树：树的子树，其所有节点的总和大于任何其他子树的总和。 编辑：节点值为整数。 我可以做以下需要O（n^2）的事情。 计算左子树中所有节点的总和 计算右子树中所有节点的总和 如果左子树和右子树的和以及根的值大于当前最大和，则根存储在结果中 以左子树作为根递归调用此函数 以右子树作为根递归调用此函数。这将需要O（n^2） 我可以将其更改为自底向上的方法，
-
问题内容： 是否真的计算了PHP数组的所有元素，还是将此值缓存在某个地方并被获取？ 问题答案： 好吧，我们可以看看源代码： call ，这反过来又需要非递归数组，该数组是通过以下方式实现的： 所以你可以看到，它的。
-
本文向大家介绍在C ++中以小于O(n)的时间在有限范围的数组中查找每个元素的频率，包括了在C ++中以小于O(n)的时间在有限范围的数组中查找每个元素的频率的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个整数数组。数组为A，大小为n。我们的任务是找到阵列中所有元素的频率小于O(n)时间。元素的大小必须小于一个等于M的值。在这里，我们将使用二进制搜索方法。在这里，如果末端元素不同，则将数组
-
问题内容： 我刚刚开始学习数据结构，并且在进行数组插入时想知道为什么数组插入的时间复杂度为O（n）而不是O（n + 1）？ 在最佳情况下，当插入在最后时，时间复杂度为O（1）。我想我们正在考虑1插入元素，因为这里没有元素被移动。在最坏的情况下，假设我们必须移动n个元素然后插入新元素，那么时间时间复杂度是否应该为O（n + 1）？n用于移动元素，1用于插入。 非常感谢您的帮助。 问题答案： O（n）