目錄
輸入
輸出
說明
方法
方法 1:透過尋找樞軸元素(最小數量)來檢查陣列是否已排序和旋轉
範例
方法 2:透過計算相鄰反轉來檢查陣列是否已排序和旋轉
結論
首頁 web前端 js教程 JavaScript程式:檢查陣列是否已排序並旋轉

JavaScript程式:檢查陣列是否已排序並旋轉

Aug 23, 2023 pm 11:37 PM

JavaScript程式:檢查陣列是否已排序並旋轉

排序陣列是所有元素都按升序排列的陣列。我們給出了一個大小為 N 的陣列和一個包含不同整數的陣列(這意味著每個整數只出現一次)。我們必須檢查陣列是否已排序並以順時針方向旋轉。這裡,如果數組已排序並旋轉,我們必須返回“YES”,否則,我們必須返回“NO”。

注意 - 這裡我們討論的是排序和旋轉意味著至少應該存在一個旋轉。我們不能將排序數組視為排序和旋轉數組。

假設我們已經給了一個大小為 N 的陣列

輸入

N = 5
Array = [5, 1, 2, 3, 4]
登入後複製

輸出

Yes, the given array is sorted and rotated. 
登入後複製

說明

陣列是已排序的陣列並旋轉 1 位元

Sorted array = [1, 2, 3, 4, 5]
Rotated above sorted array by 1 place, we get = [5, 1, 2, 3, 4]
登入後複製

按 1 個位置排序並旋轉的陣列與輸入數組匹配,因此輸出為「是」。

輸入

N = 6
Array = [6, 5, 1, 2, 3, 4]
登入後複製

輸出

No, the given array is not sorted and rotated array. 
登入後複製

說明

給定的陣列是一個未排序且旋轉的陣列

Sorted array = [1, 2, 3, 4, 5, 6]
Rotated above sorted array by 1 place, we get = [6, 1, 2, 3, 4, 5]
Rotated above sorted array by 2 place, we get = [5, 6, 1, 2, 3, 4]
Rotated above sorted array by 3 place, we get = [4, 5, 6, 1, 2, 3]
Rotated above sorted array by 4 place, we get = [3, 4, 5, 6, 1, 2]
Rotated above sorted array by 5 place, we get = [2, 3, 4, 5, 6, 1]
登入後複製

上面的排序和旋轉數組都不與輸入數組匹配,所以答案是,不。

方法

在這裡我們將討論兩種方法。讓我們在下面的部分中看到它們 -

方法 1:透過尋找樞軸元素(最小數量)來檢查陣列是否已排序和旋轉

這種方法的想法是,我們將找到最小數字,如果我們的陣列已排序並旋轉,則最小數字之前和之後的值應該以排序的方式。

範例

// function to check if the given array is sorted and rotated 
function check(arr){
   var len = arr.length;
   var mi = Number.MAX_VALUE; // variable to find the smallest number 
   var idx_min = -1; // variable to store the index of smallest number;
   
   // traversing over the array to find the minimum element and its index
   for(var i = 0; i < len; i++){
      if (arr[i] < mi){
         mi = arr[i];
         idx_min = i;
      }
   }
   
   // traversing over the array to find that all the elements 
   // before the minimum element are sorted 
   for(var i = 1; i < idx_min; i++){
      if (arr[i] < arr[i - 1]){
         return false;
      }
   }
   
   // traversing over the array to find that all the elements after the minimum element are sorted 
   for(var i = idx_min + 1; i < len; i++){
      if (arr[i] < arr[i - 1]){
         return false;
      }
   }
   
   // checking if the last element of the array is smaller than the first element or not 
   if(arr[len-1] > arr[0]){
      return false;
   }
   else{
      return true;
   }
}

// defining the array 
var arr = [5, 1, 2, 3, 4];
console.log("The given array is: ")
console.log(arr);

// calling to the function
if(check(arr)){
   console.log("Yes, the given array is sorted and rotated");
}
else{
   console.log("No, the given array is not sorted and rotated array")
}
登入後複製

時間複雜度 - O(N),其中 N 是陣列的大小。

空間複雜度 - O(1),因為我們沒有使用任何額外的空間。

方法 2:透過計算相鄰反轉來檢查陣列是否已排序和旋轉

這種方法的想法是,我們將遍歷數組並檢查前一個元素是否小於當前元素。對於已排序和旋轉的數組,如果前一個元素大於當前元素,則計數必須為 1,否則,數組不會排序和旋轉。

範例

// function to check if the given array is sorted and rotated 
function check(arr){
   var len = arr.length;
   var count = 0; // variable to count the adjacent inversions
   
   // traversing over the array to find the number of times first element is smaller than second 
   for(var i = 1; i < len; i++){
      if (arr[i] < arr[i-1]){
         count++;
      }
   }
   
   // checking if the last element of the array is smaller 
   // than the first element or not and inversion must be equal to 1
   if(arr[len-1] > arr[0] || count != 1){
      return false;
   }
   else{
      return true;
   }
}

// defining the array 
var arr = [5, 1, 2, 3, 4];
console.log("The given array is: ")
console.log(arr);

// calling to the function
if(check(arr)){
   console.log("Yes, the given array is sorted and rotated");
}
else{
   console.log("No, the given array is not sorted and rotated array")
}
登入後複製

時間複雜度 - O(N),其中 N 是陣列的大小。

空間複雜度 - O(1),因為我們沒有使用任何額外的空間。

結論

在本教程中,我們討論如何檢查陣列是否已排序和旋轉。這裡我們看到了兩種方法,第一種是找到主元(這意味著最小元素),另一種是透過計算相鄰反轉。兩種方法的時間和空間複雜度相同,分別是 O(N) 和 O(1)分別。

以上是JavaScript程式:檢查陣列是否已排序並旋轉的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

前端熱敏紙小票打印遇到亂碼問題怎麼辦? 前端熱敏紙小票打印遇到亂碼問題怎麼辦? Apr 04, 2025 pm 02:42 PM

前端熱敏紙小票打印的常見問題與解決方案在前端開發中,小票打印是一個常見的需求。然而,很多開發者在實...

神秘的JavaScript:它的作用以及為什麼重要 神秘的JavaScript:它的作用以及為什麼重要 Apr 09, 2025 am 12:07 AM

JavaScript是現代Web開發的基石,它的主要功能包括事件驅動編程、動態內容生成和異步編程。 1)事件驅動編程允許網頁根據用戶操作動態變化。 2)動態內容生成使得頁面內容可以根據條件調整。 3)異步編程確保用戶界面不被阻塞。 JavaScript廣泛應用於網頁交互、單頁面應用和服務器端開發,極大地提升了用戶體驗和跨平台開發的靈活性。

誰得到更多的Python或JavaScript? 誰得到更多的Python或JavaScript? Apr 04, 2025 am 12:09 AM

Python和JavaScript開發者的薪資沒有絕對的高低,具體取決於技能和行業需求。 1.Python在數據科學和機器學習領域可能薪資更高。 2.JavaScript在前端和全棧開發中需求大,薪資也可觀。 3.影響因素包括經驗、地理位置、公司規模和特定技能。

JavaScript難以學習嗎? JavaScript難以學習嗎? Apr 03, 2025 am 12:20 AM

學習JavaScript不難,但有挑戰。 1)理解基礎概念如變量、數據類型、函數等。 2)掌握異步編程,通過事件循環實現。 3)使用DOM操作和Promise處理異步請求。 4)避免常見錯誤,使用調試技巧。 5)優化性能,遵循最佳實踐。

如何使用JavaScript將具有相同ID的數組元素合併到一個對像中? 如何使用JavaScript將具有相同ID的數組元素合併到一個對像中? Apr 04, 2025 pm 05:09 PM

如何在JavaScript中將具有相同ID的數組元素合併到一個對像中?在處理數據時,我們常常會遇到需要將具有相同ID�...

如何實現視差滾動和元素動畫效果,像資生堂官網那樣?
或者:
怎樣才能像資生堂官網一樣,實現頁面滾動伴隨的動畫效果? 如何實現視差滾動和元素動畫效果,像資生堂官網那樣? 或者: 怎樣才能像資生堂官網一樣,實現頁面滾動伴隨的動畫效果? Apr 04, 2025 pm 05:36 PM

實現視差滾動和元素動畫效果的探討本文將探討如何實現類似資生堂官網(https://www.shiseido.co.jp/sb/wonderland/)中�...

JavaScript的演變:當前的趨勢和未來前景 JavaScript的演變:當前的趨勢和未來前景 Apr 10, 2025 am 09:33 AM

JavaScript的最新趨勢包括TypeScript的崛起、現代框架和庫的流行以及WebAssembly的應用。未來前景涵蓋更強大的類型系統、服務器端JavaScript的發展、人工智能和機器學習的擴展以及物聯網和邊緣計算的潛力。

console.log輸出結果差異:兩次調用為何不同? console.log輸出結果差異:兩次調用為何不同? Apr 04, 2025 pm 05:12 PM

深入探討console.log輸出差異的根源本文將分析一段代碼中console.log函數輸出結果的差異,並解釋其背後的原因。 �...

See all articles