• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            coding everyday

            編程面試題 https://interview.codeplex.com

            C++博客 首頁 新隨筆 聯系 聚合 管理
              12 Posts :: 2 Stories :: 7 Comments :: 0 Trackbacks

            #面試題#給定數組A,大小為n,數組元素為1n的數字,不過有的數字出現了多次,有的數字沒有出現。請給出算法和程序,統計哪些數字沒有出現,哪些數字出現了多少次。能夠在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<int10> arr = {2143565656};
            42     array_stat<10> stat(arr);
            43     stat();
            44     return 0;
            45 }

            源代碼
            posted on 2013-08-29 10:24 everyday 閱讀(710) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm面試
            性做久久久久久久久老女人| 色狠狠久久综合网| 久久精品国产亚洲av麻豆色欲 | 日韩十八禁一区二区久久| 久久丝袜精品中文字幕| 久久人妻AV中文字幕| 国产精品久久久久久一区二区三区| 99久久国产综合精品成人影院| 亚洲午夜精品久久久久久浪潮| 欧美牲交A欧牲交aⅴ久久| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 久久青青草原综合伊人| 欧美与黑人午夜性猛交久久久| 久久SE精品一区二区| 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久久久免费精品国产| 久久天天躁狠狠躁夜夜不卡| 91精品国产91久久久久久蜜臀 | 伊人久久成人成综合网222| 粉嫩小泬无遮挡久久久久久| 亚洲国产精品无码久久九九| 久久精品人人做人人爽电影| 天堂久久天堂AV色综合| 色综合久久天天综线观看| 久久er国产精品免费观看2| 伊人久久综合成人网| 中文字幕久久精品| 久久久久久久国产免费看| 久久综合久久综合久久| 久久久国产乱子伦精品作者| 久久精品卫校国产小美女| 色综合久久夜色精品国产| 亚洲精品高清一二区久久| 久久e热在这里只有国产中文精品99 | 亚洲欧美成人综合久久久| 色婷婷久久久SWAG精品| 狠狠久久综合| 色8激情欧美成人久久综合电| 久久精品成人免费国产片小草| 国产AⅤ精品一区二区三区久久 | 伊人色综合久久天天|