#面試題#給定數(shù)組A，大小為n，數(shù)組元素為1到n的數(shù)字，不過有的數(shù)字出現(xiàn)了多次，有的數(shù)字沒有出現(xiàn)。請給出算法和程序，統(tǒng)計哪些數(shù)字沒有出現(xiàn)，哪些數(shù)字出現(xiàn)了多少次。能夠在O(n)的時間復(fù)雜度，O(1)的空間復(fù)雜度要求下完成么？
想了好久，都沒能想出來算法，我覺得是不是自己走進(jìn)死胡同了，決定再看一遍題目，這一遍果然讓我發(fā)現(xiàn)，原來自己真的理解錯了題目的意思，我一開始以為要輸出多次出現(xiàn)的數(shù)字對應(yīng)的數(shù)字，所以一直都繞不過來彎。
所以有時候面試過程中，重新確認(rèn)題目還是有必要的，有時候面試緊張會誤解題目意思，當(dāng)自己沒有思路的時候，可以嘗試確認(rèn)題意，以來可以緩解一下自己的心情，再者可能面試官會跟你有更多的互動，增加好感。
確定了題意，基于之前的思考，我的算法是這樣的遍歷一遍數(shù)組，用-2,-1,0來表示沒有出現(xiàn)，出現(xiàn)一次，出現(xiàn)多次，如果當(dāng)前節(jié)點(diǎn)大于0，目標(biāo)節(jié)點(diǎn)為它對應(yīng)的值，當(dāng)前置為-2，若小于0，加一但不要超過0。算法需要一個遞歸函數(shù)（用來遞歸處理目標(biāo)節(jié)點(diǎn)一直大于0的情況，即未處理過的）和一個遍歷的函數(shù)。最終0即為多次出現(xiàn)，-1出現(xiàn)1次的，-2沒有出現(xiàn)。因為有2個前提這個算法才有效：1～n；只要出現(xiàn)多次和沒出現(xiàn)的數(shù)字，不需要次數(shù)。
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 }
源代碼