统计数组中每个元素出现的个数，时间复杂度 O(n),空间 O(1)
下面的我完全看不懂呀不知道原理是什么求各位指教呀一个长度大小为n的数组，数组中的每个元素的取值范围在[1,n]，且为正整数。
问：如何在时间复杂度为O(n)，空间复杂度为O(1)的条件下，统计数组中不同元素出现的次数。
思路：数组按序扫描，通过当前元素的值作为下标，找到下一个元素。最后得到的数组中，下标（因为下标从0开始的，故输出时需要+1）为数组中出现的元素，每个下标对应的值取反输出即是该元素出现的频率。
若当前元素小于0，
则跳过；
若当前元素大于0，
则判断其作为下标索引到的元素是否大于0，
若大于0，则索引到的元素赋值给当前元素，索引到的元素置为-1；
若小于0，则索引到的元素自减1，当前元素置为0；
#include <iostream>
using namespace std;
void work(int a[], int n)
{
int i = 0;
while(i < n)
{
int temp = a[i] - 1;
if(temp < 0)
{
i++;
continue;
}
if(a[temp] > 0)
{
a[i] = a[temp];
a[temp] = -1;
}
else
{
a[temp]--;
a[i] = 0;
}
}
}
int main()
{
int n = 10;
int *a = new int[n];
for(int i = 0; i < n; i++)
cin >> a[i];
work(a, n);
for(int i = 0; i < n; i++)
if(a[i] < 0)
cout << i + 1 << " " << (-a[i]) << endl;
cout << "********************" << endl;
delete[] a;
return 0;
}
