Edison.X. Blog

假設一 array 已經過遞增排序, 如 unsigned array[] = {1,1,2,2,2,3,5,8,8,9}，

經由下列函式

unsigned remove_dumped_memory(unsigned *array, unsigned nItem);

把所有前面之元素改成不重覆型式，並回傳有幾個不重覆。

以上為例，最後 array 會變成

{1,2,3,4,5,8,9,5,8,8,9} ，回傳 6。

解法供參考。

#include <stdio.h>

unsigned remove_dumped_memory(int *array, unsigned nItem)
{
    unsigned i, last_pos=0;
    
    if(array==NULL)
        return 0U;
    for(i=1; i<nItem; ++i)
        if(array[i]!=array[i-1])
            array[last_pos++] = array[i-1];
    if(last_pos==0 || array[last_pos-1]!=array[nItem-1])
        array[last_pos++] = array[nItem-1];
    return last_pos;
}

int main()
{
    int array[] = {1,1,2,2,2,3,5,8,9};
    unsigned n = sizeof(array) / sizeof(array[0]);
    unsigned i, cnt;

    cnt = remove_dumped_memory(array, n);
    printf("cnt = %u\n", cnt);
    for(i=0; i<cnt; ++i)
        printf("%d", array[i]);
    getchar();
    return 0;
}

有些地方是可加變化，如這裡用到的只是循序搜尋，可以應用一些其它搜尋法概念下去做，如 *2 步進 、 fib 步進等方式。問題比較大應是在第二個 if-else 那裡，在想應該有其他方式去做。