JavaScript實現身高佇列重建

在本題中，我們的任務是編寫一個JavaScript函式來實現身高佇列重建。基本上，我們要根據身高對給定的陣列資料進行排序。

理解題意

題目要求用JavaScript編寫一個函式，根據身高對佇列進行排序。這將透過佇列重建來完成。

身高佇列重建問題是根據人員的身高和在其前面身高大於或等於自身身高的人數來對人員佇列進行排序。每個人都用[h, n]表示，其中h是該人的身高，m是該人前面身高大於或等於h的人數。

任務是按照身高和m值對人員進行排序，以便重建佇列。排序身高的條件是：最高的人應該排在佇列的最前面，對於身高相同的人，k值較小的人應該排在前面。

上述問題的邏輯

給定的問題可以透過首先按身高降序對給定陣列進行排序來實現，如果身高相同，則按k值升序排序。因此，我們可以使用splice方法將排序後的人員陣列中的每個人插入到結果陣列中，插入位置由他們的k值指定。

結果陣列將包含按要求正確排序的人員。

演算法

步驟1 - 定義一個函式來按人員身高對陣列值進行排序，將其命名為reconstructQueue，並傳入一個人員陣列。

步驟2 - 在函式內部，按身高降序對人員陣列進行排序，如果身高相同，則按m值升序排序。

步驟3 - 現在建立一個空陣列來儲存排序後的佇列的結果。

步驟4 - 根據人員的m值將人員插入到結果陣列中。使用for迴圈迭代人員陣列，並使用splice方法將排序後的人員陣列中的每個人插入到結果陣列中，插入位置由他們的m值指定。

步驟5 - 獲取結果陣列的值，並返回其值以顯示重建後的佇列。

演算法程式碼

function reconstructQueue(persons) {
   // sort the persons array by descending height, and if height is same, then by ascending m
   persons.sort((a, b) => {
      if (a[0] === b[0]) {
         return a[1] - b[1];
      } else {
         return b[0] - a[0];
      }
   });
    
   let result = [];
   // insert persons into the result array according to their m value
   for (let i = 0; i < persons.length; i++) {
      result.splice(persons[i][1], 0, persons[i]);
   }
    
   return result;
}
const persons = [[7, 0],
   [4, 4],
   [7, 1],
   [5, 0],
   [6, 1],
   [5, 2]
];
const result = reconstructQueue(persons);
console.log(result);

複雜度

reconstructQueue函式的執行時間為O(n^2)，其中n是輸入陣列中人員的數量。這是因為對於陣列中的每個人，我們必須使用splice方法將他們插入到結果陣列中指定的索引處。該方法的最壞情況時間複雜度為O(n)，因為它涉及將指定索引之後的所有項向右移動一個位置。因此，整體時間複雜度為O(n^2)。該函式的空間複雜度為O(n)，因為我們建立了一個新陣列來儲存人員的最終排序結果。

結論

我們上面建立的函式根據人員的身高和m值對給定的人員陣列進行排序，並根據其順序重建佇列。reconstructQueue函式的時間複雜度為O(n^2)，空間複雜度為O(n)。

更新於：2023年5月18日

瀏覽量：159

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告