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

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

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

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

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

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

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

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