【题目】
给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。能够在O(n)的时间复杂度，O(1)的空间复杂度要求下完成么？
【分析】
我们知道原数组是没有排序的。如果排序了，很简单的。O(1)的空间含义，可以使用变量，但不能开辟数组或者map等来计数。
这个题目，很直接的解法就是两层遍历，O(n^2)的复杂度，O(1)的空间。空间满足了，但是时间没有。
很多类似的题目，都会用XOR的方法，大家仔细想一下，这个题目，可以么？或者这个题目和可以用XOR的题目的差异在哪儿？最直接的就是，每一个数字的重复的次数是不同的。
还有就是以空间换时间的方法，例如用hash map或者数组来计数。时间满足了，但是空间没有满足。
那怎样才能有时间复杂度O(n)，空间复杂度O(1)的算法呢？不能开辟新的空间，那么只剩下，重复利用数组A。那么该如何利用数组A呢？
（1）首先，我们介绍一种三次遍历数组的方法,我们都考虑数组从0开始：
第一次遍历：对于每一个A[i] = A[i] * n
第二次遍历：对于每一个i，A[A[i]/n]++
第三次遍历：对于每一个i，A[i] % n就是出现次数
A[i]应该出现在A中的A[i]位置，乘以n、再除以n，很容易的来回变换；第二次遍历，对于A[i]本来所在的位置不断增1，但绝对不对超出n的，那每一个i出现的次数，就是A[i]对n取余。
（2）还有一种两次遍历的方法，也是上面的思路：题目中数组是1到n，为了方便算法考虑，以及数组存储方便，我们考虑0-n-1，结果是相同的。 考虑A[i]，现在位置是i，如果采用A来计数，它的位置应该是A[i] % n，找到计数位置，该如何处理这个位置呢？加1么？ 显然不可以，这里有一个技巧，就是加n，有两个原因
加n可以保证A[i] % n是不变的
A数组，最后每一个元素表示为A[i] = x + k*n，其中x<n，并且k就是我们要统计的频率。
这样，大家也能够明白，为什么A[i]在A中的位置，表示为A[i] % n了吧。
【代码】
#include <iostream>
#include <malloc.h>
#include <stdio.h>
using namespace std;
//统计数组重复元素个数
void ArrayNumCount(int array[],int n){
int i;
if(n <= 0 || array == NULL){
return;
}
for(i = 0;i < n;i++){
array[i] *= n;
}
for(i = 0;i < n;i++){
array[array[i]/n]++;
}
for(i = 0;i < n;i++){
array[i] %= n;
}
//输出
//array[0]存储值为n的个数
int element;
for(i = 0;i < n;i++){
if(i == 0){
element = n;
}
else{
element = i;
}
printf("Element:%d Count:%d\n",element,array[i]);
}
}
int main() {
int array[] = {2,3,1,2,4,3,5,3,5,8};
ArrayNumCount(array,10);
return 0;
}
#include <iostream>
#include <malloc.h>
#include <stdio.h>
using namespace std;
//统计数组重复元素个数
void ArrayNumCount(int array[],int n){
int i;
if(n <= 0 || array == NULL){
return;
}
for(i = 0;i < n;i++){
array[array[i]%n]+=n;
}
//输出
//array[0]存储值为n的个数
int element,count;
for(i = 0;i < n;i++){
count = array[i] / n;
element = i;
if(i == 0){
element = n;
}
printf("Element:%d Count:%d\n",element,count);
}
}
int main() {
int array[] = {2,3,1,2,4,3,5,3,5,8,11};
ArrayNumCount(array,11);
return 0;
}
