C++程序 计算旋转次数以使给定数组按非递增顺序排序

C++程序 计算旋转次数以使给定数组按非递增顺序排序

给定一个由 N 个整数组成的数组 arr[] ,任务是通过最小数量的逆时针旋转将数组按非递增顺序排序。如果不能对数组进行排序,则打印 “-1” 。否则,打印旋转的计数。

示例:

输入: arr[] = {2, 1, 5, 4, 3}

输出: 2

说明: 需要两次逆时针旋转才能将数组按降序排序,即{5, 4, 3, 2, 1}

输入: arr[] = {2, 3, 1}

输出: -1

方法: 想法是遍历给定的数组 arr[] 并计算满足 **arr[i + 1] > arr[i] ** 的索引数。按照以下步骤解决问题:

  • 将 **arr[i + 1] > arr[i] ** 的数量计数,并将 **arr[i+1] > arr[i] ** 时的索引存储在变量中。
  • 如果 计数 的值为 N – 1 ,则数组按非递减顺序排序。所需步骤正好为 (N – 1)
  • 如果 计数 的值为 0 ,则数组已经按非递增顺序排序。
  • 如果 计数 的值为 1arr[0] ≤ arr[N – 1] ,则所需的旋转次数等于 (index + 1) ,通过对该索引之前的所有数字执行移动来实现。还要检查 arr[0] ≤ arr[N – 1] ,以确保序列是非递增的。
  • 否则,不能将数组按非递增顺序排序。

下面是上述方法的实现:

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to count minimum anti-
// clockwise rotations required to
// sort the array in non-increasing order
void minMovesToSort(int arr[], int N)
{
    // Stores count of arr[i + 1] > arr[i]
    int count = 0;
  
    // Store last index of arr[i+1] > arr[i]
    int index;
  
    // Traverse the given array
    for (int i = 0; i < N - 1; i++) {
  
        // If the adjacent elements are
        // in increasing order
        if (arr[i] < arr[i + 1]) {
  
            // Increment count
            count++;
  
            // Update index
            index = i;
        }
    }
  
    // Print the result according
    // to the following conditions
    if (count == 0) {
        cout << "0";
    }
    else if (count == N - 1) {
        cout << N - 1;
    }
    else if (count == 1
             && arr[0] <= arr[N - 1]) {
        cout << index + 1;
    }
  
    // Otherwise, it is not
    // possible to sort the array
    else {
        cout << "-1";
    }
}
  
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 1, 5, 4, 2 };
    int N = sizeof(arr)
            / sizeof(arr[0]);
  
    // Function Call
    minMovesToSort(arr, N);
  
    return 0;
}  

输出:

2

时间复杂度: O(N)

辅助空间: O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例