0

この関数は、小石を表す文字配列を受け取り、その配列を RED、WHITE、および BLUE の文字に再配置します。再配置中に行われたスワップの数も返されます。入力が正当で、再配置が成功した場合、関数は 1 を返します。入力に不正な文字が見つかった場合は 0 を返します。

boolean processInput(char *pebbles, int *noOfSwaps){

    int low;
    int mid;
    int high;

    *noOfSwaps = 0;

    low = 0;

    while (low < strlen(pebbles) && color(*(pebbles + low)) == RED)
            low++;

    high = strlen(pebbles) - 1;

    while (high >= 0 && color(*(pebbles + high)) == BLUE)
            high--;

    mid = low;

    while (mid <= high){

            if (color(*(pebbles + mid)) == RED){

                    if (mid == low){

                            low++;
                            mid++;
                    }

                    else{

                            swap((pebbles + mid), (pebbles + low));

                            (*noOfSwaps)++;
                            low++;
                            mid++;
                    }
            }

            else if (color(*(pebbles + mid)) == WHITE)
                    mid++;

            else if (color(*(pebbles + mid)) == BLUE){
                    if (color(*(pebbles + high)) == BLUE)
                            high--;

                    else{
                            swap((pebbles + mid), (pebbles + high));
                            (*noOfSwaps)++;
                            high--;
                    }
            }      
            else
                    return 0;
    }
    return 1;
}

^^^私のコードは上にあります。たった一つの機能。その関数の最悪の場合の複雑さと理由を知る必要があります。ありがとう！

4

1 に答える 1

1

この線はO(n) + O(color())、すべての小石が赤いときに最小限になります。色がO(1)（おそらくそうです）の場合、それはただO(n)：

while (low < strlen(pebbles) && color(pebbles[low]) == RED)
    low++;

コードの残りの部分は、各要素の色を1回だけ検査しているように見えるので、それO(n) + O(color())も同様です。

だから私はと行きO(n)ます。

編集：それをスクラッチし、彼はstrlenそのwhileループを呼び出します。これをにアップグレードしますO(n^2)。nの長さはどこですかpebbles。これをに戻すのは簡単O(n)です。一度呼び出しstrlen()て、値をキャッシュします。

于 2013-03-10T02:43:06.867 に答える