C++程序检查在旋转数组后是否可以对其进行排序

背景

先来了解一下旋转数组是什么。旋转数组指的是将一个有序数组的某个部分移到数组的头部或尾部，类似于旋转木马的原理。例如，原始的有序数组为[1,2,3,4,5]，其旋转一个位置后为[5,1,2,3,4]。

我们现在面临的问题是如何判断这个旋转后的数组是否可以进行排序。

方法

我们可以先将旋转数组想象成一个二分搜索树的模型。其组成方式是：根节点为数组中的中心（下标为len/2，如果数组长度为奇数）或者中心偏左一个（下标为len/2-1，如果数组长度为偶数）。然后将左侧变成左子树，右侧变成右子树。在递归中，例如左子树大小为l，右子树大小为r，那么根节点的左右子树可以竖直分别写出本次构建的旋转数组的左右部分，注意不是原来数组的左右部分，总长为l+r+1。

接下来再判断合法性，只要左右子树都合法，且左子树最大值小于等于根节点，右子树最小值大于等于根节点，那么就返回该子树大小。

下面我们实现数组是否可以旋转的代码。

class Solution {
public:
    bool check(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len; ++i) {
            if (nums[i] > nums[(i + 1) % len]) {
                return is_sorted(nums.begin(), nums.begin() + i + 1) && is_sorted(nums.begin() + i + 1, nums.end());  
            }
        }
        return true;
    }
};

接下来我们就可以利用上面的二分搜索树的模型快速判断是否可以排序了。判断递归到底的唯一条件是，左右子树的大小加起来等于当前子树大小。注意到我们要求的是排序后的数组，所以要使用自己写的快排。

class Solution {
public:
    void qsort(vector<int>& nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int i = l, j = r, p = nums[(l + r) / 2];
        while (i <= j) {
            while (nums[i] < p) {
                ++i;
            }
            while (nums[j] > p) {
                --j;
            }
            if (i <= j) {
                swap(nums[i], nums[j]);
                ++i;
                --j;
            }
        }
        qsort(nums, l, j);
        qsort(nums, i, r);
    }
    bool check(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len; ++i) {
            if (nums[i] > nums[(i + 1) % len]) {
                vector<int> v1(nums.begin(), nums.begin() + i + 1);
                vector<int> v2(nums.begin() + i + 1, nums.end());
                qsort(v1, 0, v1.size() - 1);
                qsort(v2, 0, v2.size() - 1);
                merge(v1.begin(), v1.end(), v2.begin(), v2.end(), nums.begin());
                return is_sorted(nums.begin(), nums.end());  
            }
        }
        return true;
    }
};

示例

下面是一些例子来说明这个题目的解决方法。

int main() {
    Solution s;
    vector<int> nums = {3,4,5,1,2};
    cout << s.check(nums) << endl; // expect true

    nums = {2,1,3,4,5};
    cout << s.check(nums) << endl; // expect true

    nums = {1,2,1,2,1,2};
    cout << s.check(nums) << endl; // expect true

    nums = {4,5,6,7,0,1,2};
    cout << s.check(nums) << endl; // expect true

    nums = {3,2,1};
    cout << s.check(nums) << endl; // expect false

    nums = {4,3,2};
    cout << s.check(nums) << endl; // expect false

    return 0;
}