统计数组中不同元素出现的次数（时间复杂度O(n)，空间复杂度o(1)）
乐视笔试题：
一个长度大小为n的数组，数组中的每个元素的取值范围在[1,n]，且为正整数。
问：如何在时间复杂度为O(n)，空间复杂度为O(1)的条件下，统计数组中不同元素出现的次数。
思路：数组按序扫描，通过当前元素的值作为下标，找到下一个元素。最后得到的数组中，下标（因为下标从0开始的，故输出时需要+1）为数组中出现的元素，每个下标对应的值取反输出即是该元素出现的频率。
若当前元素小于0，
则跳过；
若当前元素大于0，
则判断其作为下标索引到的元素是否大于0，
若大于0，则索引到的元素赋值给当前元素，索引到的元素置为-1；
若小于0，则索引到的元素自减1，当前元素置为0；
代码如下：
#include <iostream> #include <algorithm> #include <vector> #include <queue>#include <stack>#include <string> #include <string.h> #include <fstream> #include <map> #include <iomanip> #include <cstdio> #include <cstdlib>#include <cmath>#include <deque>#include <hash_map>using namespace std; const int MAX = 0x7FFFFFFF; const int MIN = 0x80000000; 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;while(cin >> n){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;}system("pause");return 0;}