2017年1月27日 星期五

求中位數

對本題感興趣的原因是覺得與 LeetCode 4. Median of Two Sorted Arrays 有關,以為先練成求單一陣列中位數,會比較知道求兩個陣列的中位數該怎麼做(不過這樣的線性思考似乎沒什麼用...)

冼鏡光老師的 C 名題精選百則,問題 5-6 求中位數裡已經有詳細解答。但筆者在研究該解答時發現一件怪事,在大量測試下,有時得出的中位數與排序後得到的中位數不一樣。

下面為測試程式,與冼老師解答使用的演算法 100% 一樣(5-24頁),只是改用 C++ 實作:
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace::std;

void swap(int& a, int& b)
{
    const int tmp = a;
    a = b;
    b = tmp;
}

void split(vector<int>& v, int first, int last, int& split_point)
{
    const int split_data = v[first];
    split_point = first;
    for(int i = first + 1; i <= last && split_point <= last; ++i)
    {
        if(v[i] < split_data)
        {
            ++split_point;
            swap(v[split_point], v[i]);
        }
    }

    swap(v[first], v[split_point]);
}

int median(vector<int>& v)
{
    int left = 0;
    int right = v.size() - 1;
    const int middle = (left+right)/2;
    int split_point;
    while(1)
    {
        split(v, left, right, split_point);
        if(split_point == middle)
            break;
        else if(split_point > middle)
            right = split_point - 1;
        else
            left = split_point + 1;
    }
    
    if((v.size()%2) != 0)    
        return v[middle];
    else
        return (v[middle]+v[middle+1])/2; 
}

int main(int argc, char *argv[])
{
    using namespace::std;
    
    srand(time(0));
    for(int i = 0; i < 10000; ++i)
    {

        vector<int> v;
        while(v.size()==0)
            v.resize(rand()%1000);

        for(size_t i = 0; i < v.size(); ++i)
            v[i] = rand();

        vector<int> v2 = v;
        int median1 = median(v);

        sort(v2.begin(), v2.end());
        const int middle = (v2.size() - 1)/2;
        int median2;
        if((v2.size()%2) != 0)
            median2 = v2[middle];
        else
            median2 = (v2[middle]+v2[middle+1])/2;

        if(median1 != median2)
        {
            printf("median1=%d,median2=%d\n", median1, median2);
            printf("oops!\n");            
            break;
        }
    }
    
    return 0;
}
程式的精髓是 Line 7. split(),以三步驟將陣列劃分:

Step 1.



Step 2.



Step 3.



接著,Line 41-46 依據 < split_data 與 >= split_data 哪塊比較長來決定如何調整 left 或 right,如果 Line 40 取得的 split_point 等於 middle,則中斷 Line 38. while loop,得到答案。

後來找了很久,才知道要等 left 與 right 交會時中斷 Line 38. while loop 才是對的,程式修改如下:
int median(std::vector<int>& v)
{
    //...
    while(1)
    {
        split(v, left, right, split_point);
        if(left >= right)
            break;
        else if(split_point > middle)
            right = split_point - 1;
        else
            left = split_point + 1;
    }
        
    //...
}
至於「為什麼?」筆者也還在思考中,只能說演算法真的是很深奧的學問,寫出程式還不是最難的,要證明一隻程式 100% 正確無誤很難...

沒有留言:

張貼留言