資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學檢查C++中陣列是否已排序並旋轉
給定一個整數陣列，任務是檢查陣列是否已排序（升序）並在某個位置之後旋轉。
例如
輸入1
N = [7, 8, 9, 4, 5, 6]
輸出
True
說明：由於給定的陣列是升序排列的，並且第3個位置之後的元素已旋轉，因此在這種情況下我們將返回True。
輸入2
N = [1, 5, 7, 6, 2, 3]
輸出
False
說明：由於給定的陣列既不是升序排列的，也不是在特定位置旋轉的，因此輸出為False。
解決此問題的方法
我們有一個元素要麼升序排列要麼未排序的陣列。如果陣列必須排序並旋轉，則至少會存在一個元素使得 N[i] > N[i+1]。
因此，對於每個N[i]，我們將計算滿足條件的元素個數，並相應地返回True或False。
- 輸入陣列元素。
- 布林函式checkSortedandRotated(int *arr, int n)接受一個數組及其大小作為輸入，如果陣列已排序並旋轉則返回true，否則返回false。
- 遍歷整個陣列並計算滿足(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個位置旋轉，因此在這種情況下輸出為'True'。
更新於： 2021年2月23日
2K+ 瀏覽量
廣告