在过去的一个月里，关于我的算法决赛的最后一个问题一直让我发疯。这是问题：
你有一个数组
A[0...n]，写一个算法（在“适当的”伪代码中）在 O(n) 中运行，它可以确定这个数组是否已经相对于某个索引进行了分区k，如果是，findk; 如果不是，则返回 -1；
为了澄清，通过Partition：
对于 中的每个元素
e，A[0...n]如果e < A[k]放在e的“左侧”A[k]，则放在e的“右侧”A[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;
}