在C ++中的O(1)空间中以元素0到N-1的常量数组查找重复项

假设我们有一个从0到n-1的数字列表。一个数字可以重复多次。我们必须找到重复的数字而不占用任何额外的空间。如果n = 7,则list类似于[5,2,3,5,1,6,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

以上是 在C ++中的O(1)空间中以元素0到N-1的常量数组查找重复项 的全部内容, 来源链接: utcz.com/z/331394.html

回到顶部