JavaScript 重建队列的高度

在这个问题的陈述中, 我们的任务是通过Javascript编写一个根据身高重建队列的函数。因此，基本上我们需要按照给定的数组数据按身高排序。

理解问题陈述

问题陈述中说要在Javascript中写一个函数，帮助我们按照身高来排序队列。这将通过队列重建来实现。

身高重新构建队列问题是通过根据他们的身高和在他们前面的相同身高或更高身高的人数来排列一个人队列的问题。每个人用[h，n]来表示，其中h是这个人的身高，n是在身高大于或等于h的人的前面的人数。

任务是以一种队列按照他们的身高和m值重建队列的方式对人进行排序。排列身高的条件是：最高的人应该在队列的前面，而在相同高度的人中，那些具有较小的k值的人将被先放在前面。

上述问题的逻辑

可以通过首先将给定的数组按身高降序排列，如果身高相同，则按k值升序排列来实现给定的问题。因此，我们可以使用splice方法将排序后的人数组中的每个人插入到结果数组的由其k值指定的索引中。

结果数组将以所需的正确顺序包含人员。

算法

第一步 −定义一个函数来根据人的身高安排数组值，并命名为reconstructQueue，并传递一个人的数组。

第二步 −在函数内部，通过对身高进行降序排序人的数组，并且如果身高相同，则按照m的升序顺序排列。

第三步 −现在创建一个空数组，用于存储排序后队列的结果。

第四步 −根据其m值，将个人插入结果数组中。使用for循环遍历个人数组，并使用splice方法，我们可以将排序后的每个人从个人数组插入到结果数组中，插入位置由其m值指定的索引处。

第五步 −获取结果数组的值，并将其返回以显示重建的队列。

算法的代码

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)，因为我们创建了一个新的数组来存储具有最终排序顺序的人员。