プログラミング演習 : 12/15 の演習で聞いたアルゴリズムたち

※注意:これは内輪ネタです.

1.文字列中に任意の文字があるかを探す関数

自分の回答

int str_char(const char s[], int c)
{
    int index = 0;

    while (s[index]) {
        if (s[index] == c) {
            return c;
        }
    }

    return -1;
}

return を一つしか用いない回答

int str_char(const char s[], int c)
{
    int index = 0;
    int count = -1;

    while (s[index]) {
        if (s[index] == c) {
            count = index
            break;
        }
    }

    return count;
}

2.文字列から数字文字を除去する関数

自分の回答

void del_num(char* s)
{
    int index = 0;

    while (s[index]) {
        if (s[index] >= '0' && s[index] <= '9') {
            int j;
            for (j = index; s[j]; j ++) {
                s[j] = s[j + 1];
            }
        }
        else {
            index ++;
        }
    }

    return;
}

効率が非常にいい素晴らしい回答

void del_num(char* s)
{
    int index = 0;
    int putindex = 0;

    while (s[index]) {
        if (s[index] >= '0' && s[index] <= '9') {
            //何もしない
        }
        else {
            char buf; //副作用対策
            buf = s[index];
            s[putindex] = buf;
            putindex ++;
        }

        index ++;
    }
    //末尾にナル文字付与
    s[putindex] = '\0';

    return;
}

自分のは  O(n^2) だが, これは  O(n) で終わる. かなりの速度差である.

今回はここまで

Raptor