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

Question

在过去的一个月里，关于我的算法期末考试的最后一个问题一直让我抓狂。问题是：

您有一个数组A[0...n]，编写一个在O（n）中运行的算法（以"正确"的伪代码），该算法可以确定该数组是否已经相对于某个索引k进行了分区，如果是，则查找k；如果不是，则返回-1；

澄清，通过Partition:

对于A[0...n]中的每个元素e，如果e < A[k]将e放在A[k]的"左边"，否则将e放在A[k]的"右边"。

分区数组的一个例子（w.r.t.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 : %cn", maxIdx, A[maxIdx], i, A[i], (isPart?'T':'F'));
        if( A[minIdx] > A[i] ) { isPart = false; }
        printf("A[%d] = %d <==> A[%d]: %d : %cn", minIdx, A[minIdx], i, A[i], (isPart?'T':'F'));
    }
    printf("A[%d] = %d : %cnn", 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:TA[0]=10<===>A[0]：10:TA[1]=20<===>A[1]:20:TA[0]=10<===>A[1]:20:TA[2]=30<===>A[2]：30:TA[0]=10<===>A[2]：30:TA[3]=40<===>A[3]：40:TA[0]=10<===>A[3]：40:TA[3]=40<===>A[4]：11:FA[4]=11<===>A[4]：11:FA[5]=100<===>A[5]：100:TA[5]=100<===>A[5]：100:TA[6]=150<===>A[6]：150:TA[5]=100<===>A[6]：150:TA[6]=150<===>A[7]:101:FA[7]=101<===>A[7]:101:FA[6]=150<===>A[8]:125:FA[8]=125<===>A[8]:125:FA[5]=100:F<--索引是正确的。。。但是isPart是错误的
未分区>：//pre>
我真的很想今晚能睡觉，所以任何提示/提示/想法等都将不胜感激。
哇@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]，这几乎就是分区的定义。

Answer 2

有趣的问题

在我看来，必须有可能在不需要使用额外缓冲空间的情况下解决这个问题。

我们知道，如果有一个枢轴元素，那么

• （未知）枢轴位置左侧的所有元素都小于或等于枢轴元素
• （未知）枢轴位置右侧的所有元素都大于或等于枢轴元素

由此我们知道

• 枢轴左侧的所有元素小于或等于枢轴右侧的任何元素，以及
• 枢轴右侧的所有元素都大于或等于枢轴左侧的任何元素

这种情况的一个特殊情况是

• 枢轴左侧的所有元素都小于或等于最右侧的元素
• 枢轴右侧的所有元素都大于或等于最左侧的元素

使用这样的理由，我们应该能够递归地"回到"枢轴位置，如果有的话。

伪代码：

Set highest value found on low side to value of first element
Set lowest value found on high side to value of last element
Set low index to first element
Set high index to last element
repeat
  increment low index
  if low index >= array length -> fail
  if value at new low index > highest so far on the low side
    set new highest-on-low-side value
      if new value greater than lowest value so far on right side,
        set low index back to what it was and mark it as stuck
        set highest-on-low-side value back to what it was
  decrement high index
  if high index < 0 -> fail
  if value at new high index < lowest so far on the high side
    set new lowest-on-high-side value
      if new value less than the highest value so far on the left side,
        set high index back to what it was and mark it as stuck
        set lowest-on-high-side value back to what it was
until both low and high index is stuck or until low index >= high index
if low index = high index
  pivot position = low index
else
  failure

这是一个实际的Pascal实现，我曾用一些测试输入来简要验证这个想法，但目前我没有时间进行全面的验证。

function PivotIndex(a: array of integer): Integer;
var
  HighestValueOnLeftSide: Integer;
  LowestValueOnRightSide: Integer;
  LowIndex: Integer;
  HighIndex: Integer;
  LowStuck, HighStuck: Boolean;
begin
  HighestValueOnLeftSide := -1;
  LowestValueOnRightSide := MaxInt;
  LowIndex := -1;
  HighIndex := length(a);
  LowStuck := False;
  HighStuck := False;
  repeat
    if not LowStuck then begin
      inc(LowIndex);
      if LowIndex >= length(A) then begin
        Result := -1;
        exit;
      end;
      if A[LowIndex] > HighestValueOnLeftSide then
        if A[LowIndex] > LowestValueOnRightSide then begin
          LowStuck := True;
          dec(LowIndex);
        end else
          HighestValueOnLeftSide := A[LowIndex];
    end;
    if not HighStuck then begin
      dec(HighIndex);
      if HighIndex < 0 then begin
        Result := -1;
        exit;
      end;
      if A[HighIndex] < LowestValueOnRightSide then
        if A[HighIndex] < HighestValueOnLeftSide then begin
          HighStuck := True;
          inc(HighIndex);
        end else
          LowestValueOnRightSide := A[HighIndex];
    end;
  until LowStuck and HighStuck or (LowIndex >= HighIndex);
  if LowIndex = HighIndex then
    Result := LowIndex
  else
    Result := -1;
end;

我相信这可以变得更加优雅和高效，但如果你发现它有任何直接的问题，请告诉我。