資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究JavaScript 程式檢查是否可以透過旋轉陣列進行排序
旋轉陣列意味著將每個索引的元素（不包括一端）移動到右旋轉的下一個索引和左旋轉的上一個索引。對於右旋轉，第零個索引取最後一個索引的值，反之亦然，對於左旋轉。排序陣列意味著所有元素都按正確的升序排列。我們將實現正確的程式碼，並進行解釋以及時間和空間複雜度討論。
示例
Input: 5 6 9 10 2 3 3 4 Output: Yes
說明：我們可以將給定陣列旋轉 4 次以獲得排序陣列。
First Rotation: 4 5 6 9 10 2 3 3 Second Rotation: 3 4 5 6 9 10 2 3 Third Rotation: 3 3 4 5 6 9 10 2 Fourth Rotation: 2 3 3 4 5 6 9 10
樸素方法
在這種方法中，主要思想是，在旋轉次數等於陣列長度後，我們將獲得相同的陣列。因此，我們將旋轉陣列等於其長度的次數，並且對於每次旋轉，我們將使用雙指標和交換方法。在每次旋轉時，我們將檢查當前陣列是否已排序。
示例
// function to rotate the given array
function rotate(arr){
var l = 0;
var r = arr.length-1;
while(l < r){
arr[l] += arr[r];
arr[r] = arr[l]-arr[r];
arr[l] = arr[l]-arr[r];
l++;
}
return arr;
}
// function to check if the given array is increasing or not
function increasing(arr){
// getting the size of array
var len = arr.length
// traversing over the array
for(var i = 1; i < len; i++){
if(arr[i] < arr[i-1]){
return false;
}
}
return true;
}
// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
var k = arr.length
while(k--){
if(increasing(arr)){
console.log("The given array can be sorted after " + (arr.length-k-1) + " rotations");
return
}
arr = rotate(arr);
}
console.log("The given array cannot be sorted");
}
//defining the given array
var arr = [5, 6, 9, 10, 2, 3, 3, 4]
console.log("Given array is: " + arr);
// calling the function
check(arr);
輸出
Given array is: 5,6,9,10,2,3,3,4 The given array can be sorted after 4 rotations
時間和空間複雜度
上述程式碼的時間複雜度為 O(N*N)，其中 N 是陣列的大小。我們正在旋轉陣列 N 次，每次旋轉需要 N 次移動。
上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。
有效方法
先前程式碼的時間複雜度很高，可以透過觀察來降低，如果給定陣列已排序或分為兩部分，則第二部分的元素小於或等於第一部分，並且兩部分本身都是排序的。
示例
// function to check if the given array is increasing or not
function increasing(arr){
// getting the size of the array
var len = arr.length
// traversing over the array
var i = 0;
for(var i = 1; i < len; i++){
if(arr[i] < arr[i-1]){
break;
}
}
if(i == len) return true;
i++;
for(; i< len; i++){
if(arr[i] < arr[i-1]){
return false;
}
}
return arr[len-1] <= arr[0];
}
// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
if(increasing(arr)){
console.log("The given array can be sorted after ");
}
else{
console.log("The given array cannot be sorted");
}
}
//defining the given array
var arr = [5, 4, 9, 10, 2, 3, 3, 4]
console.log("Given array is: " + arr);
// calling the function
check(arr);
輸出
Given array is: 5,4,9,10,2,3,3,4 The given array cannot be sorted
時間和空間複雜度
上述程式碼的時間複雜度為 O(N)，其中 N 是陣列的大小。我們只遍歷陣列一次。
上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。
結論
在本教程中，我們實現了 JavaScript 程式碼來檢查我們是否可以透過旋轉其元素來對元素進行排序。旋轉陣列意味著將每個索引的元素（不包括一端）移動到右旋轉的下一個索引和左旋轉的上一個索引。我們實現了兩種方法，一種時間複雜度為 O(N*N)，另一種為 O(N)。
更新於： 2023年4月13日
72 次檢視
廣告