彈吉他寫C++: Finding the redundant number in an array with fixed range elements

假設輸入一個陣列具有101個數, 數字分布範圍是1到100, 找出重複的數
Solution: linear search, sum, ... O(n)

假設傳入的陣列為sorted
Solution: Binary Search O(log n)

e.g.
b m e
0 1 2 3 4 5
1 1 2 3 4 5
index值與element值相同, 往左找, b = b, e = m

b m e
0 1 2  3 4 5
1 2 3  4 4 5
index值與element值不相同, 往右找, b = m, e = e

終止條件: b與e的元素相同, 或是 e == b+1
e.g.
0 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 9 10

pass1:
b m e
0 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8  9  9  10

pass2:
b m e
0 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8  9  9  10

pass3:
b m e
0 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8  9  9  10

pass4:
b m e
0 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8  9  9  10

pass4:
b e
0 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8  9  9  10
return 9

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

void shuffle( int *a, int n ){
    int pickedLoc;
    while( n != 0 ){
        // choose a location "pickedLoc" to exchange
        // the element on location n-1 with "pickedLoc"
        pickedLoc = rand( ) % n--;

        // swap
        int temp = a[n];
        a[n] = a[pickedLoc];
        a[pickedLoc] = temp;
    }
}

int find_redundant_linear( int *a, const int n ){
    if( !a || n < 2 ) return -1;
    bool *flag = new bool[n](); // flag[0] is unused

    for( int i = 0 ; i < n ; ++i )
        flag[a[i]] = !flag[a[i]];

    for( int i = 0 ; i < n ; ++i )
        if( !flag[a[i]] ){
            delete [] flag;
            return a[i];
        }
}

int find_redundant_binarySearch( int *a, const int n ){
    if( !a || n < 2 ) return -1;

    int begin = 0;
    int end = n-1;
    int middle;
    while( end != begin + 1 ){
        middle = (begin + end) / 2;
        if( a[middle] == middle )
            end = middle;
        else
            begin = middle;
    }
    return a[begin];
}

int main( ){

    // initialize an array with N numbers within [1, N-1]
    // and only one number is redundant in this array
    const int N = 101;
    int arr[N];
    int *p = arr;
    int *q = arr + sizeof(arr)/sizeof(arr[0]);
    int count = 1;
    while( p != q )
        *p++ = count++;

    // create a redundant number
    srand( time(NULL) );
    arr[N-1] = rand( ) % (N-1) + 1;
    cout << "The redundant number is " << arr[N-1] << endl;

    // shuffle them
    shuffle( arr, N );

    // find redundant
    int r = find_redundant_linear( arr, N );
    cout << "The found redundant number is " << r << endl;

    // sort the array
    p = arr;
    sort( p, q );
    r = find_redundant_binarySearch( arr, N );
    cout << "The found redundant number is " << r << endl;
}

遇到這個問題, 最麻煩的部分是, 知道如何iteration下去, 可是不知道boundary condition怎麼取

方法就是, 找一個很小的例子來觀察 (其實作法就跟數學歸納法的證明一樣), 考慮n小一點的case, 例如 1 個或 2 個inputs, 就是很 trivial 的 case

例如, 此問題就可以考慮當 input 只有 2 個時的case,
index 0 1
element 1 1
顯然終止是在 e == b+1時

只要假設且確保原問題的 input 數量是會 down 此case的即可

彈吉他寫C++

2014年3月7日星期五

Finding the redundant number in an array with fixed range elements

沒有留言:

張貼留言

2014年3月7日 星期五

Finding the redundant number in an array with fixed range elements

沒有留言:

張貼留言

2014年3月7日星期五