题目描述

1. 给定数组A，大小为N，数字元素为1~N的int数，但是有些数字出现多次，有些数字没出现，统计出哪些数字出现了多次，哪些数字没有出现，要求额外空间使用O(1)，时间O(N)。

解题思路

1. 第一次遍历：对于每一个A[i] = A[i] * n。
2. 第二次遍历：对于每一个i，A[A[i]/n]++。
3. 第三次遍历：对于每一个i，A[i] % n就是出现次数。

#include <iostream>
#include <vector>
using namespace std;

// 模拟的数组
vector<int> arr = {1, 3, 1, 1, 3, 5, 4, 2, 6, 7};

int main()
{
    int n = arr.size();

    // 第一步：为每个元素乘上 n
    for(auto& e : arr) e *= n;      // 10 30 10 10 30 50 40 20 60 70 

    // 第二步：a[a[i] / n]++
    for(int i = 0; i < n; ++i)
    {
        arr[arr[i] / n]++;
    }                               // 10 33 11 12 31 51 41 21 60 70

    // 第三步：扫描数组，得出结果
    for(int i = 0; i < n; ++i)
    {
        int num = arr[i] % n;
        cout << i << " 出现的次数为 " << num << endl;
    }                               // 0 3 1 2 1 1 1 1 0 0


    return 0;
}