Cho một mảng các số nguyên, nhiệm vụ là kiểm tra xem mảng có được sắp xếp (thứ tự tăng dần) và xoay vòng sau một số vị trí hay không.
Ví dụ
Đầu vào-1:
N = [7, 8, 9, 4, 5, 6]
Đầu ra:
True
Giải thích: Vì mảng đã cho có thứ tự tăng dần và các phần tử sau vị trí thứ 3 được xoay vòng, chúng tôi sẽ trả về True trong trường hợp này.
Đầu vào-2:
N = [1, 5, 7, 6, 2, 3]
Đầu ra:
False
Giải thích: Vì mảng đã cho không theo thứ tự tăng dần hoặc không được xoay theo một số vị trí cụ thể, nên kết quả đầu ra là Sai.
Phương pháp tiếp cận để giải quyết vấn đề này
Chúng ta có một mảng với phần tử theo thứ tự tăng dần hoặc không được sắp xếp. Nếu mảng phải được sắp xếp và xoay vòng thì sẽ có ít nhất một phần tử ở đó sao cho N [i]> N [i + 1].
Do đó, với mọi N [i], chúng tôi sẽ tính xem có phần tử nào thỏa mãn điều kiện không và trả về True hoặc False tương ứng.
- Lấy đầu vào của một phần tử mảng.
- Một hàm Boolean checkSortedandRotated (int * arr, int n) nhận một mảng và kích thước của nó làm đầu vào và trả về true nếu mảng được sắp xếp và xoay ngược lại là false.
- Lặp lại trên toàn bộ mảng và đếm số phần tử là (arr [i]> arr [i + 1]% n). Nếu số lượng là '1' thì trả về True, ngược lại trả về False.
- Trả lại đầu ra.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
bool checkSortedandRotated(int * arr, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > arr[(i + 1) % n])
count++;
}
return (count <= 1);
}
int main() {
int arr[] = {5,6,7,1,2,3,4};
int n = sizeof(arr) / sizeof(int);
if (checkSortedandRotated(arr, n)) {
cout << "True" << endl;
} else {
cout << "False" << endl;
}
return 0;
} Chạy đoạn mã trên sẽ tạo ra kết quả là,
Đầu ra
True
Vì mảng đã cho [5, 6, 7, 1, 2, 3, 4] được sắp xếp và xoay từ vị trí thứ 3, chúng tôi nhận được kết quả là 'Đúng' trong trường hợp này.