在O(n)时间和O(1)额外空间中寻找重复项- C++中的集合1

假设我们有一个从0到n-1的数字列表。数字可以尽可能重复多次。我们必须在不占用任何额外空间的情况下找出重复的数字。如果n = 7，并且列表像[5, 2, 3, 5, 1, 6, 2, 3, 4, 5]。答案将是5、2、3。

要解决此问题，我们必须遵循以下步骤−

对列表中的每个元素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

Arnab Chakraborty

更新于： 2019-11-01

239 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始学习