如何判断已排序旋转数组的升降序？求Python实现（用于旋转次数计算）

首先我们明确前提：假设数组元素无重复（若有重复，逻辑需额外调整，后文会说明），且由严格升序或严格降序的数组经过若干次旋转得到（这里统一以向左旋转次数为标准，即每次旋转将第一个元素移到尾部）。

步骤1：判断数组的基础排序方向 #

我们可以通过统计相邻元素的增减趋势来判断：

• 若所有相邻元素都是递增的：这是未旋转的升序数组，旋转次数为0。
• 若所有相邻元素都是递减的：这是未旋转的降序数组，旋转次数为0。
• 若只有一组相邻元素是递增的，其余都是递减的：这是降序旋转数组（原数组为严格降序，经旋转得到）。
• 若只有一组相邻元素是递减的，其余都是递增的：这是升序旋转数组（原数组为严格升序，经旋转得到）。

步骤2：基于方向的二分查找计算旋转次数 #

升序旋转数组的旋转次数 #

升序旋转数组的向左旋转次数等于数组中最小值的索引。我们用二分查找快速定位最小值：

• 当arr[mid] > arr[right]时，说明最小值在mid右侧（右半部分无序）。
• 否则，最小值在mid或左侧（右半部分有序）。

降序旋转数组的旋转次数 #

降序旋转数组的向左旋转次数等于数组长度减去最大值的索引。同样用二分查找定位最大值：

• 当arr[mid] < arr[right]时，说明最大值在mid右侧（左半部分无序）。
• 否则，最大值在mid或左侧（右半部分有序）。

Python实现代码 #

def determine_rotation_info(arr):
    n = len(arr)
    if n <= 1:
        return {"direction": "ascending", "rotation_count": 0}  # 短数组方向无意义，旋转次数为0
    
    # 统计相邻元素的增减次数
    inc_count = 0
    dec_count = 0
    for i in range(n-1):
        if arr[i] < arr[i+1]:
            inc_count += 1
        elif arr[i] > arr[i+1]:
            dec_count += 1
    
    # 判断方向并计算旋转次数
    if inc_count == n-1:
        return {"direction": "ascending", "rotation_count": 0}
    elif dec_count == n-1:
        return {"direction": "descending", "rotation_count": 0}
    elif inc_count == 1:
        # 降序旋转数组：找最大值索引
        left, right = 0, n-1
        while left < right:
            mid = (left + right) // 2
            if arr[mid] < arr[right]:
                left = mid + 1
            else:
                right = mid
        max_index = left
        # 向左旋转次数 = 数组长度 - 最大值索引；向右旋转次数直接取max_index即可
        return {"direction": "descending", "rotation_count": n - max_index}
    elif dec_count == 1:
        # 升序旋转数组：找最小值索引
        left, right = 0, n-1
        while left < right:
            mid = (left + right) // 2
            if arr[mid] > arr[right]:
                left = mid + 1
            else:
                right = mid
        min_index = left
        return {"direction": "ascending", "rotation_count": min_index}
    else:
        # 存在多个增减点，不符合严格旋转排序数组的要求
        raise ValueError("Input array is not a strictly rotated sorted array (ascending or descending)")

# 测试示例
if __name__ == "__main__":
    # 升序旋转示例
    arr1 = [5, 6, 1, 2, 3, 4]
    result1 = determine_rotation_info(arr1)
    print(f"数组{arr1}: 方向={result1['direction']}, 向左旋转次数={result1['rotation_count']}")
    
    # 降序旋转示例
    arr2 = [2, 1, 6, 5, 4, 3]
    result2 = determine_rotation_info(arr2)
    print(f"数组{arr2}: 方向={result2['direction']}, 向左旋转次数={result2['rotation_count']}")
    
    # 未旋转的升序数组
    arr3 = [1,2,3,4,5]
    result3 = determine_rotation_info(arr3)
    print(f"数组{arr3}: 方向={result3['direction']}, 向左旋转次数={result3['rotation_count']}")
    
    # 未旋转的降序数组
    arr4 = [5,4,3,2,1]
    result4 = determine_rotation_info(arr4)
    print(f"数组{arr4}: 方向={result4['direction']}, 向左旋转次数={result4['rotation_count']}")

补充说明 #

• 若需要向右旋转次数，对于降序旋转数组直接返回最大值索引即可；升序旋转数组的向右旋转次数为n - min_index。
• 若数组包含重复元素，统计增减次数的方法会失效（比如[2,2,2,1,2]），此时需要通过比较首尾、中间元素推断方向，同时修改二分查找条件以处理重复值。

内容的提问来源于stack exchange，提问作者user9790132