#面试题#给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。能够在O(n)的时间复杂度，O(1)的空间复杂度要求下完成么？
想了好久，都没能想出来算法，我觉得是不是自己走进死胡同了，决定再看一遍题目，这一遍果然让我发现，原来自己真的理解错了题目的意思，我一开始以为要输出多次出现的数字对应的数字，所以一直都绕不过来弯。
所以有时候面试过程中，重新确认题目还是有必要的，有时候面试紧张会误解题目意思，当自己没有思路的时候，可以尝试确认题意，以来可以缓解一下自己的心情，再者可能面试官会跟你有更多的互动，增加好感。
确定了题意，基于之前的思考，我的算法是这样的遍历一遍数组，用-2,-1,0来表示没有出现，出现一次，出现多次，如果当前节点大于0，目标节点为它对应的值，当前置为-2，若小于0，加一但不要超过0。算法需要一个递归函数（用来递归处理目标节点一直大于0的情况，即未处理过的）和一个遍历的函数。最终0即为多次出现，-1出现1次的，-2没有出现。因为有2个前提这个算法才有效：1～n；只要出现多次和没出现的数字，不需要次数。
1 #include <iostream>
2 #include <array>
3 using namespace std;
4
5 template<int N>
6 class array_stat {
7 public:
8 array_stat(const array<int, N>& arr) : m_arr(arr) {
9 }
10
11 void operator()() {
12 for (int i=1; i<=N; i++) {
13 process(i);
14 }
15
16 for (int i=0; i<N; i++) {
17 if (m_arr[i] == 0)
18 cout << i+1 << " exists more than once" << endl;
19 else if (m_arr[i] == -2)
20 cout << i+1 << " doesnt exist" << endl;
21 }
22 }
23 private:
24 array<int, N> m_arr;
25
26 void process(int i) {
27 if (m_arr[i-1] > 0) {
28 int cur = m_arr[i-1];
29 m_arr[i-1] = -2;
30 process(cur);
31 }
32 else {
33 m_arr[i-1]++;
34 if (m_arr[i-1] > 0)
35 m_arr[i-1] = 0;
36 }
37 }
38 };
39
40 int main() {
41 array<int, 10> arr = {2, 1, 4, 3, 5, 6, 5, 6, 5, 6};
42 array_stat<10> stat(arr);
43 stat();
44 return 0;
45 }
源代码