时间戳

首页 > 解决方案 > 对数组进行排序并检索排序后的索引

arrays - 对数组进行排序并检索排序后的索引

问题描述

我想按他的索引对数组进行排序。

看下面的代码：

var distances = [530, 0, 24, 335, 274, 591];

console.log(sortIndex(distances));

function sortIndex(toSort) {
  return toSort.map(
    (e,i) => {return {index: i, value: e};}
  ).sort(
    (a,b) => a.value - b.value
  ).map(
    (e,i) => {return e.index;},[]
  );
}

输出是：

[1, 2, 4, 3, 0, 5]

有人能告诉我如何降低这个片段的复杂性吗？这个算法是O(n^3)，我想知道你是否可以用更好的解决方案来解决同样的问题？

外面有人吗？谢谢。

标签： arraysalgorithmsortingindexingtime-complexity

解决方案

您可以通过创建数组和索引结构来获得更好的性能，其中复杂性在于我们只迭代数组一次。copyhashO(N)

var distances = [530, 0, 24, 335, 274, 591];
var copy = Object.assign([], distances);

var indexes = distances.reduce((hash, elem, i) => {
  hash[elem] = i;
  return hash;
}, {});

sortIndex = (toSort) => toSort.sort().map(el => indexes[el]);
console.log(sortIndex(copy));

所以，算法的最终复杂度是函数的复杂度sort加上map函数的复杂度。

因为sort复杂度是Θ(n log(n))。

对于该map方法，复杂性是O(n)因为您只迭代一次数组以通过提供的函数映射每个项目。callback

推荐阅读