时间戳

首页 > 解决方案 > 检查是否存在索引 k 使得数组 A[] 的元素顺时针移动形成一个反向双调数组

arrays - 检查是否存在索引 k 使得数组 A[] 的元素顺时针移动形成一个反向双调数组

问题描述

检查是否存在索引，使得由索引顺时针移动0 <= k < n - 2的数组元素构成一个反向双调数组。我在O(n)时间复杂度中做到这一点的方法：A[]k

bool is_antibitonicable(int A[], int n) {
    // returns if there is such index k that 
    // after moving clockwise k elements of array
    // A[], that array is reverse bitonic
    // - strictly decreasing then strictly
    // increasing
    if (n < 3)
        return false;
    // if is_increasing[i] == 1 means this part of A[] is increasing,
    // == 0 means that part of A[] is decreasing, == -1 default
    int is_increasing[3] = { -1, -1, -1 };
    for (int i = 0, j; i < n - 1;) {
        if (A[i] < A[i + 1]) { // if A[] is increasing
            j = 0;
            while (j < 3 && is_increasing[j] != -1)
                j++;
            if (j == 3)
                return false;
            is_increasing[j] = 1;
            while (i < n - 1 && A[i] < A[i + 1])
                i++;
        }
        else if (A[i] > A[i + 1]) { // check if decreasing
            j = 0;
            while (j < 3 && is_increasing[j] != -1)
                j++;
            if (j == 3)
                return false;
            is_increasing[j] = 0;
            while (i < n - 1 && A[i] > A[i + 1])
                i++;
        }
        else // sequence of A[] is neither increasing nor decreasing
            return false;
    }
    // if A[] is only increasing/decreasing
    if (is_increasing[1] == is_increasing[2])
        return false;
    // if A[] is increasing->decreasing->increasing check if increasing
    // parts can be merged into one increasing sequence
    if (is_increasing[0] == 1 && is_increasing[1] == 0 && is_increasing[2] == 1)
        return (A[0] > A[n - 1]);
    // decreasing->increasing->decreasing
    if (is_increasing[0] == 0 && is_increasing[1] == 1 && is_increasing[2] == 0)
        return (A[0] < A[n - 1]);
    return true; // increasing -> decreasing or opposite
}

如果有人可以查看我的解决方案并评论它是否正确或如何做得更好，我将非常高兴，任何反馈将不胜感激。

标签： arrayscalgorithmverification

解决方案

您的解决方案看起来不错，但确实不正确return false // if A[] is only increasing/decreasing。这样的序列总是可以通过在正确（适当的）方向上旋转一个而变成第一个减少然后增加一个。

推荐阅读