アルゴリズムのファイナルに関する最後の質問は、この 1 か月間私を夢中にさせてきました。質問は次のとおりです。
array があり
A[0...n]、O(n) で実行されるアルゴリズムを (「適切な」疑似コードで) 記述します。このアルゴリズムは、この配列が既に何らかのインデックスに対して分割されているかどうかを判断できkますk。そうでない場合は -1 を返します。
明確にするために、によってPartition：
の各要素について、 の「左」に配置する場合
eは、そうでない場合は の「右」に配置します。A[0...n]e < A[k]eA[k]eA[k]
したがって、分割された配列の例 (wrt k = 11):
A = [4 2 5 3 7 4 2 6 8 4 11010 10 20 11 15 13 28 99 11]
それから
myAlgo(A) -> (11)
また
A = [10, 20, 30, 40, 11,100, 150, 101, 125]
それから
myAlgo(A) -> (5)
だがしかし：
A = [10, 20, 30, 40, 5]
myAlgo(A) -> (-1)
私の最初の考え（信じられないほどナイーブだった）は、文字通り言葉にできないほどひどかった. 基本的に、配列がソートされているかどうかを誤ってチェックし、かなりランダムな値を真ん中から取り出しました。
私の次の考えは、リストをスキャンし、最初にヒットした最大の数値を見つけてから、減少する数値をヒットしてそれらの数値をすべて除外することでした...基本的に最大値と最小値を保持し、両方の外にある場合は、可能性のあるパーティション インデックスをサブセットの最後にシフトします。
これを（テストケースで）実装しようと（非常にひどく）試みた場所は次のとおりです。
int myAlgo(const int* A, int n);
int main() {
const int A[] = {10, 20, 30, 40, 11, 100, 150, 101, 125};
int index;
if((index = myAlgo(A, 9)) != -1) {
printf("A[%d] = %d", index, A[index]);
}
else {
printf("Not Partitioned >:/");
}
return 0;
}
int myAlgo(const int* A, int n) {
// the index of the smallest possible number in the remainder of the list
int minIdx = 0;
// the index of the largest number we've encountered
int maxIdx = 0;
// index of possible partition "center"
int kIdx = 0;
bool isPart = false;
for(int i=0; i < n; ++i) {
if( A[maxIdx] <= A[i] ) {
maxIdx = i;
if(isPart == false) { kIdx = i; minIdx = i;} // if we flipped then this is a good time to grab a partitioner index
isPart = true;
}
else { isPart = false; minIdx = i; }
printf("A[%d] = %d <==> A[%d]: %d : %c\n", maxIdx, A[maxIdx], i, A[i], (isPart?'T':'F'));
if( A[minIdx] > A[i] ) { isPart = false; }
printf("A[%d] = %d <==> A[%d]: %d : %c\n", minIdx, A[minIdx], i, A[i], (isPart?'T':'F'));
}
printf("A[%d] = %d : %c\n\n", kIdx, A[kIdx], (isPart?'T':'F'));
// We gotta check this to make sure it is a valid list...
if(isPart) return kIdx;
else return -1;
}
しかし、当然のことながら、私の出力は次のとおりです。
A[0] = 10 <==> A[0]: 10 : T
A[0] = 10 <==> A[0]: 10 : T
A[1] = 20 <==> A[1]: 20 : T
A[0] = 10 <==> A[1]: 20 : T
A[2] = 30 <==> A[2]: 30 : T
A[0] = 10 <==> A[2]: 30 : T
A[3] = 40 <==> A[3]: 40 : T
A[0] = 10 <==> A[3]: 40 : T
A[3] = 40 <==> A[4]: 11 : F
A[4] = 11 <==> A[4]: 11 : F
A[5] = 100 <==> A[5]: 100 : T
A[5] = 100 <==> A[5]: 100 : T
A[6] = 150 <==> A[6]: 150 : T
A[5] = 100 <==> A[6]: 150 : T
A[6] = 150 <==> A[7]: 101 : F
A[7] = 101 <==> A[7]: 101 : F
A[6] = 150 <==> A[8]: 125 : F
A[8] = 125 <==> A[8]: 125 : F
A[5] = 100 : F <-- The index is right... but isPart is wrong
Not Partitioned >:/
今夜はぐっすり眠りたいので、ヒント/ヒント/アイデア/その他を教えていただければ幸いです。
ウー！@Amitは私の問題を解決するのに役立ちました.これが私の更新された関数です:
int partIdx2(const int* A, int n) {
int* max = malloc(n * sizeof(int));
int* min = malloc(n * sizeof(int));
for(int i=0; i < n; i++)
{
if(i==0) {
max[i] = A[i];
min[n - 1] = A[n-1];
}
else {
max[i] = MAX(max[i-1], A[i]);
min[n - 1 - i] = MIN(min[n - 1 - i + 1], A[n - 1 - i]);
}
}
for(int i=1; i < n-1; i++) {
if(A[i] >= max[i-1] && A[i] <= min[i+1]) {
free(max);
free(min);
return i;
}
}
free(max);
free(min);
return -1;
}