【八十一題題目合集 微軟面試100題 第八十一題】

題目要求：

　　問題1：在一個int數組裡查找這樣的數，它大于等于左側所有數，小于等于右側所有數。

　　問題2：一個檔案，内含一千萬行字元串，每個字元串在1k以内，要求找出所有相反的串對，如abc和cba。

　　問題3：STL的set用什麼實作的？為什麼不用hash？

題目分析：

　　問題1分析：

　　　　假設int數組為data[]。

　　　　用兩個數組a、b作為輔助數組，a[i]、b[i]分别儲存從左到i最大的數和從右到i的最小數，需要周遊兩次data。

　　　　然後再周遊一遍原數組data[]，将所有的data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。

　　　　-----改進-------

　　　　不要b數組，初始化a數組之後，直接倒序周遊data{]，用一個臨時變量min儲存到目前為止的最小數，然後找出滿足data[i]>=a[i-1]&&data[i]<=min的即可。

　　　　結果：少周遊了一次數組data，少了一個輔助數組b[]。

　　問題2分析：

　　　　1000W*1k = 10G.

　　　　根據實際記憶體，把該檔案的資料hash散列到n個小檔案file,每個小檔案大小大約為10G%n.hash(string)%n = k(其中k∈[0,n)，然後把該string放入到file[k]中

　　　　把小檔案依次讀進記憶體存入set<string>中，每次讀入的字元串倒序後到set<string>中查找，如果有則輸出，同時删除set<string>中的該字元串；如果沒有則把輸入的字元串壓入到set<string>中。

　　問題3分析：　　

　　　set底層實作方式為RB樹（即紅黑樹），紅黑樹之後會在部落格中專題講解，主要對紅黑樹插入和删除用僞碼的形式講解。

    首先set，不像map那樣是key-value對，它的key與value是相同的。關于set有兩種說法，第一個是STL中的set，用的是紅黑樹；第二個是hash_set，底層用的是hash table。紅黑樹與hash table最大的不同是，紅黑樹是有序結構，而hash table不是。但不是說set就不能用hash，如果隻是判斷set中的元素是否存在，那麼hash顯然更合适，因為set 的通路操作時間複雜度是log(N)的，而使用hash底層實作的hash_set是近似O(1)的。然而，set應該更加被強調了解為“集合”，而集合所涉及的操作并、交、差等，即STL提供的如交集set_intersection()、并集set_union()、差集set_difference()和對稱差集set_symmetric_difference()，都需要進行大量的比較工作，那麼使用底層是有序結構的紅黑樹就十分恰當了，這也是其相對hash結構的優勢所在。

代碼實作：

問題1代碼

#include <iostream>

using namespace std;

void Find(int *data,int n);

int main(void)
{
    int data[] = {3,2,6,9,8};
    Find(data,5);

    data[4] = 12;
    Find(data,5);
    return 0;
}
void Find(int *data,int n)
{
    if(data==NULL || n<=0)
        return ;
    int *a = new int[n];
    int *b = new int[n];

    int max = data[0];
    a[0] = data[0];
    for(int i = 1;i<n;i++)
    {
        if(data[i]>max)
            max = data[i];
        a[i] = max;
    }

    int min = data[n-1];
    b[n-1] = data[n-1];
    for(int i = n-2;i>=0;i--)
    {
        if(data[i]<min)
            min = data[i];
        b[i] = min;
    }
    
    cout << "滿足的元素有:";
    for(int i = 1;i<n;i++)
    {
        if(data[i]>=a[i-1] && data[i]<=b[i])
            cout << data[i] << " ";
    }
    cout << endl << "-----------------" << endl;
}      

問題1改進代碼

#include <iostream>

using namespace std;

void Find(int *data,int n);

int main(void)
{
    int data[] = {3,2,6,9,8};
    Find(data,5);

    data[4] = 12;
    Find(data,5);
    return 0;
}
void Find(int *data,int n)
{
    if(data==NULL || n<=0)
        return ;
    int *a = new int[n];
    int *b = new int[n];

    int max = data[0];
    a[0] = data[0];
    for(int i = 1;i<n;i++)
    {
        if(data[i]>max)
            max = data[i];
        a[i] = max;
    }

    int min = data[n-1];
    
    cout << "滿足的元素有:";
    for(int i = n-1;i>=1;i--)
    {
        if(data[i]<min)
            min = data[i];
        if(data[i]>=a[i-1] && data[i]<=min)
            cout << data[i] << " ";
    }
    cout << endl << "-----------------" << endl;
}      

轉載于:https://www.cnblogs.com/tractorman/p/4119350.html