เมื่อกำหนดอาร์เรย์ของจำนวนเต็ม ภารกิจคือตรวจสอบว่ามีการจัดเรียงอาร์เรย์ (เพิ่มขึ้น) และหมุนตามจำนวนตำแหน่งหรือไม่
ตัวอย่าง
อินพุต-1:
N = [7, 8, 9, 4, 5, 6]
ผลลัพธ์:
True
คำอธิบาย: เนื่องจากอาร์เรย์ที่ระบุอยู่ในลำดับที่เพิ่มขึ้นและองค์ประกอบหลังจากหมุนตำแหน่งที่ 3 เราจะคืนค่า True ในกรณีนี้
อินพุต-2:
N = [1, 5, 7, 6, 2, 3]
ผลลัพธ์:
False
คำอธิบาย: เนื่องจากอาร์เรย์ที่ระบุไม่อยู่ในลำดับที่เพิ่มขึ้นหรือหมุนด้วยตำแหน่งเฉพาะ เอาต์พุตจึงเป็นเท็จ
แนวทางในการแก้ปัญหานี้
เรามีอาร์เรย์ที่มีองค์ประกอบในลำดับที่เพิ่มขึ้นหรือไม่มีการเรียงลำดับ หากต้องจัดเรียงและหมุนอาร์เรย์ อย่างน้อยหนึ่งองค์ประกอบจะอยู่ที่นั่นเพื่อให้ N[i]> N[i+1].
ดังนั้น สำหรับทุก N[i] เราจะนับว่ามีองค์ประกอบใดที่ตรงตามเงื่อนไขและคืนค่าเป็นจริงหรือเท็จตามนั้น
- รับอินพุตขององค์ประกอบอาร์เรย์
- ฟังก์ชันบูลีน checkSortedandRotated(int *arr, int n) รับอาร์เรย์และขนาดของอาร์เรย์เป็นอินพุตและคืนค่า จริง หากอาร์เรย์ถูกจัดเรียงและหมุนเป็นเท็จ
- วนซ้ำทั่วทั้งอาร์เรย์และนับจำนวนองค์ประกอบที่เป็น (arr[i]> arr[i+1]%n) หากการนับคือ '1' ให้คืนค่า True ไม่เช่นนั้นให้คืนค่า False
- ส่งคืนผลลัพธ์
ตัวอย่าง
#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;
} การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
ผลลัพธ์
True
เนื่องจากอาร์เรย์ที่ระบุ [5, 6, 7, 1, 2, 3, 4] ถูกจัดเรียงและหมุนจากตำแหน่งที่ 3 เราจึงได้ผลลัพธ์เป็น 'จริง' ในกรณีนี้
