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