在 O(1) 空间内使用 C++ 搜索常量数组中的重复项，其中元素为 0 到 N-1

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

为了解决这个问题，我们必须按照以下步骤执行操作 −

  • 对列表中的每个元素 e 执行以下步骤 −
    • sign := 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

更新时间:18-12-2019

210 次浏览

开启你的 职业

完成课程获得认证

开始
广告