算法问题 - 确定数组是否已被分区(即快速排序的一步)

Question

关于我的算法决赛的最后一个问题让我在过去一个月里疯狂.这是一个问题:

你有一个数组A[0...n],编写一个在O(n)中运行的算法(在"正确的"伪代码中),该算法可以确定该数组是否已经相对于某个索引进行了分区k,如果是,则查找k; 如果没有则返回-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;
}

Answer 1

一个O(n)时间+空间的解决办法是有两个阵列,max和min.

max[i] = max{arr[0],arr[1],...,arr[i]}
min[i] = min{arr[i],arr[i+1],...,arr[n-1]}

请注意,您可以使用线性时间创建两个数组.

拥有这些数组后,您需要查找是否存在以下索引k:

arr[k] >= max[k-1] && arr[k] <= min[k+1]

这也可以在线性时间内完成

这是有效的,因为如果上述成立,那么后面的每个元素k都保证更高或等于arr[k],并且之前的每个元素都更低或等于arr[k],这几乎是分区的定义.