資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 程式：檢查是否可以透過旋轉陣列使其遞增或遞減
陣列的旋轉是指將陣列視為迴圈陣列，並將陣列的元素向左或向右旋轉一個索引，每次旋轉一個索引，並且一端的一個元素可能取另一端的值。遞增陣列表示每個元素都大於或等於其前一個元素，遞減陣列表示每個元素都小於或等於其前一個元素。
在這個問題中，我們給定一個數組，我們可以向左或向右旋轉陣列，我們必須找到是否在某些旋轉（可能是零）之後我們可以使陣列遞增或遞減。
樸素方法
在這種方法中，我們將旋轉陣列，並在每次旋轉時檢查當前陣列是否遞增或遞減。
示例
在下面的示例中，我們檢查是否可以透過旋轉給定陣列使其遞增或遞減。以下是輸入和預期輸出。
輸入：arr = [3, 4, 5, 6, 1, 2]
預期輸出：是
輸入：arr = [ 5, 1, 6, 2, 5, 3 ]
預期輸出：否
示例
// 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 if the given array is decreasing or not
function decreasing(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) || decreasing(arr)){
return true;
}
arr = rotate(arr);
}
return false;
}
// defining the arr's
var arr1 = [3, 4, 5, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
輸出
The given array is: [ 3, 4, 5, 6, 1, 2 ] Yes, after some rotations given array can be transformed into an increasing or decreasing array The given array is: [ 5, 1, 6, 2, 5, 3 ] No, after some rotations given array cannot be transformed into an increasing or decreasing array
上述程式碼的時間複雜度為 O(N*N)，空間複雜度為 O(1)。
高效方法
在前面的陣列中，我們檢查了每次旋轉陣列是否遞增或遞減，在這種方法中，我們將部分檢查陣列是否遞增或遞減。
示例
// 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
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 if the given array is decreasing or not
function decreasing(arr){
// getting the size of 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) || decreasing(arr)){
return true;
}
else{
return false;
}
}
// defining the arr's
var arr1 = [3, 4, 7, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
輸出
The given array is: [ 3, 4, 7, 6, 1, 2 ] No, after some rotations given array cannot be transformed into an increasing or decreasing array The given array is: [ 5, 1, 6, 2, 5, 3 ] No, after some rotations given array cannot be transformed into an increasing or decreasing array
上述程式碼的時間複雜度為 O(N)，空間複雜度為 O(1)。
結論
在本教程中，我們實現了一個 JavaScript 程式，用於檢查是否可以透過旋轉給定陣列使其遞增或遞減。我們實現了兩種方法，時間複雜度分別為 O(N*N) 和 O(N)，並且兩種方法的空間複雜度均為 O(1)。
更新於： 2023年4月13日
113 次檢視
廣告