• <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面試
            久久精品中文闷骚内射| 国产69精品久久久久9999| 久久无码中文字幕东京热| 亚洲av成人无码久久精品| 大伊人青草狠狠久久| 久久久久国产亚洲AV麻豆| 伊人久久大香线蕉综合影院首页| 久久久一本精品99久久精品88| 久久电影网2021| 亚洲午夜久久久久久噜噜噜| 天天久久狠狠色综合| 一本久道久久综合狠狠爱| 久久久久国产日韩精品网站| 精品少妇人妻av无码久久| 午夜精品久久久久成人| 亚洲狠狠综合久久| 国产精品久久久久jk制服| 久久精品一区二区三区AV| 久久久久久一区国产精品| 亚洲一区二区三区日本久久九| 精品国产乱码久久久久软件| 亚洲国产成人久久综合碰| 久久精品国产亚洲网站| 久久99精品国产自在现线小黄鸭 | 久久亚洲精品中文字幕| 93精91精品国产综合久久香蕉| 国产精品一久久香蕉国产线看观看 | 久久综合久久综合久久综合| 无码AV波多野结衣久久| 中文字幕久久亚洲一区| 一本一本久久a久久精品综合麻豆| 久久99精品久久久久久噜噜| 成人久久精品一区二区三区 | 日韩人妻无码一区二区三区久久99 | 欧美精品一区二区精品久久| 99久久精品国产麻豆| 丁香五月网久久综合| 国产精品久久久久久久| 亚洲国产精品久久66| 欧美激情精品久久久久久久九九九| 久久国产香蕉一区精品|