我在將這個解決方案從 O(n^2) 轉換為 O(n) 時遇到了一些問題。任何人都可以幫忙嗎？我想不出任何方法來使時間復雜度為 O(n)。
//MERGE SORTED ARRAY
/*arr1 = [0,3,4,31]
arr2 = [4,6,30]*/
const mergeSortedArrays = (arr1, arr2) => {
let arr = [];
let flag = true;
// MERGING ARRAYS
for (let i = 0; i < arr1.length; i ) {
arr.push(arr1[i]);//PUSHING ARRAY1 in arr
}
for (let i = 0; i < arr2.length; i ) {
arr.push(arr2[i]);//PUSING ARRAY2 in arr
}
//SORTING ARRAYS
while (flag) {
for (let i = 0; i < arr.length; i ) {
if (arr[i] > arr[i 1]) {
let temp = arr[i 1];
arr[i 1] = arr[i];
arr[i] = temp;
flag = true;
} else {
flag = false;
}
}
}
console.log(arr1);
console.log(arr2);
console.log(arr);//FINAL MERGED & SORTED ARRAY
// return arr;
}
mergeSortedArrays([0, 3, 4, 31], [4, 6, 30]);uj5u.com熱心網友回復：
嘗試將其可視化。就好像你有兩疊要排序的卡片。您可以比較每個堆疊頂部的卡片，并將較小的值放在第三個堆疊上。并重復，直到所有卡片都在第三個排序的堆疊上。
您可以保留兩個指標，i并且j，每個陣列一個。這將模擬堆疊。
演算法：
Repeat until the end of both arrays is reached:
if arr1[i] <= arr2[j]
push arr1[i] to the merged array and increment i
else
push arr2[j] to the merged array and increment j
還有一些javascript代碼：
let merged = [];
let i = 0;
let j = 0;
while(i < arr1.length || j < arr2.length){
if(j == arr2.length || (i < arr1.length && arr1[i] <= arr2[j])){
merged.push(arr1[i]);
i ;
} else{
merged.push(arr2[j]);
j ;
}
}
uj5u.com熱心網友回復：
您可以使用兩個指標方法，（此解決方案基于兩個串列將始終排序的假設）
p1=0,p2=0;
arr=[];
while(p1<arr1.length && p2<arr2.length)
{
if(arr1[p1]<arr2[p2])
arr.push(arr1[p1 ];
else
arr.push(arr2[p2 ];
}
while(p1<arr1.length)
arr.push(arr1[p1 ]);
while(p2<arr2.length)
arr.push(arr2[p2 ];
此代碼將以 O(N) 的時間復雜度運行。我不熟悉 JS，所以請更正任何語法錯誤。
uj5u.com熱心網友回復：
你可以只用Array#concat()和Array#sort()提高圈復雜度
代碼：
const mergeSortedArrays = (arr1, arr2) => arr1
.concat(arr2)
.sort((a, b) => a - b)
const result = mergeSortedArrays([0, 3, 4, 31], [4, 6, 30])
console.log(result)轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/478669.html
標籤：javascript 数组 排序 数据结构 时间复杂度
上一篇：加號不上下移動