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中文網其他相關文章!

熱AI工具

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

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

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

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

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

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

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

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

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

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

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

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

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