Tìm số vòng quay trong mảng được sắp xếp đã xoay trong C ++

Hãy xem xét chúng ta có một mảng, là mảng đã được sắp xếp xoay vòng. Chúng ta phải tìm số lần xoay được yêu cầu để sắp xếp mảng. (Chúng tôi sẽ xem xét việc xoay từ phải sang trái.)

Giả sử mảng có dạng:{15, 17, 1, 2, 6, 11} thì ta phải xoay mảng hai lần để sắp xếp. Thứ tự cuối cùng sẽ là {1, 2, 6, 11, 15, 17}. Ở đây đầu ra là 2.

Logic rất đơn giản. Nếu để ý, chúng ta có thể thấy rằng số vòng quay cũng giống như giá trị chỉ số của phần tử tối thiểu. Vì vậy, nếu chúng ta nhận được phần tử tối thiểu, thì chỉ mục của nó sẽ là kết quả.

Ví dụ

#include <iostream>
using namespace std;
int getMinIndex(int arr[], int n){
   int index = 0;
   for(int i = 1; i<n; i++){
      if(arr[i] < arr[index]){
         index = i;
      }
   }
   return index;
}
int countNumberOfRotations(int arr[], int n){
   return getMinIndex(arr, n);
}
int main() {
   int arr[] = {15, 17, 1, 2, 6, 11};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Number of required rotations: " << countNumberOfRotations(arr, n);
}

Đầu ra

Number of required rotations: 2