目錄
輸入
輸出
說明
方法
方法 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

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

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

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

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

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

熱門話題

Java教學
1666
14
CakePHP 教程
1425
52
Laravel 教程
1325
25
PHP教程
1273
29
C# 教程
1252
24
JavaScript引擎:比較實施 JavaScript引擎:比較實施 Apr 13, 2025 am 12:05 AM

不同JavaScript引擎在解析和執行JavaScript代碼時,效果會有所不同,因為每個引擎的實現原理和優化策略各有差異。 1.詞法分析:將源碼轉換為詞法單元。 2.語法分析:生成抽象語法樹。 3.優化和編譯:通過JIT編譯器生成機器碼。 4.執行:運行機器碼。 V8引擎通過即時編譯和隱藏類優化,SpiderMonkey使用類型推斷系統,導致在相同代碼上的性能表現不同。

Python vs. JavaScript:學習曲線和易用性 Python vs. JavaScript:學習曲線和易用性 Apr 16, 2025 am 12:12 AM

Python更適合初學者,學習曲線平緩,語法簡潔;JavaScript適合前端開發,學習曲線較陡,語法靈活。 1.Python語法直觀,適用於數據科學和後端開發。 2.JavaScript靈活,廣泛用於前端和服務器端編程。

從C/C到JavaScript:所有工作方式 從C/C到JavaScript:所有工作方式 Apr 14, 2025 am 12:05 AM

從C/C 轉向JavaScript需要適應動態類型、垃圾回收和異步編程等特點。 1)C/C 是靜態類型語言,需手動管理內存,而JavaScript是動態類型,垃圾回收自動處理。 2)C/C 需編譯成機器碼,JavaScript則為解釋型語言。 3)JavaScript引入閉包、原型鍊和Promise等概念,增強了靈活性和異步編程能力。

JavaScript和Web:核心功能和用例 JavaScript和Web:核心功能和用例 Apr 18, 2025 am 12:19 AM

JavaScript在Web開發中的主要用途包括客戶端交互、表單驗證和異步通信。 1)通過DOM操作實現動態內容更新和用戶交互;2)在用戶提交數據前進行客戶端驗證,提高用戶體驗;3)通過AJAX技術實現與服務器的無刷新通信。

JavaScript在行動中:現實世界中的示例和項目 JavaScript在行動中:現實世界中的示例和項目 Apr 19, 2025 am 12:13 AM

JavaScript在現實世界中的應用包括前端和後端開發。 1)通過構建TODO列表應用展示前端應用,涉及DOM操作和事件處理。 2)通過Node.js和Express構建RESTfulAPI展示後端應用。

了解JavaScript引擎:實施詳細信息 了解JavaScript引擎:實施詳細信息 Apr 17, 2025 am 12:05 AM

理解JavaScript引擎內部工作原理對開發者重要,因為它能幫助編寫更高效的代碼並理解性能瓶頸和優化策略。 1)引擎的工作流程包括解析、編譯和執行三個階段;2)執行過程中,引擎會進行動態優化,如內聯緩存和隱藏類;3)最佳實踐包括避免全局變量、優化循環、使用const和let,以及避免過度使用閉包。

Python vs. JavaScript:社區,圖書館和資源 Python vs. JavaScript:社區,圖書館和資源 Apr 15, 2025 am 12:16 AM

Python和JavaScript在社區、庫和資源方面的對比各有優劣。 1)Python社區友好,適合初學者,但前端開發資源不如JavaScript豐富。 2)Python在數據科學和機器學習庫方面強大,JavaScript則在前端開發庫和框架上更勝一籌。 3)兩者的學習資源都豐富,但Python適合從官方文檔開始,JavaScript則以MDNWebDocs為佳。選擇應基於項目需求和個人興趣。

Python vs. JavaScript:開發環境和工具 Python vs. JavaScript:開發環境和工具 Apr 26, 2025 am 12:09 AM

Python和JavaScript在開發環境上的選擇都很重要。 1)Python的開發環境包括PyCharm、JupyterNotebook和Anaconda,適合數據科學和快速原型開發。 2)JavaScript的開發環境包括Node.js、VSCode和Webpack,適用於前端和後端開發。根據項目需求選擇合適的工具可以提高開發效率和項目成功率。

See all articles