如何有效地对数组进行排序 [英] How to sort an array efficiently

问题描述

我正在尝试将数组 [3,3,2,1,3,2,2,2,1] 排序为 [1,1,3,3，3,2,2,2,2] .

I'm trying to sort an array [3,3,2,1,3,2,2,2,1] to [1,1,3,3,3,2,2,2,2].

我正在尝试使用对象来处理它，将数字用作键，并将出现的值用作值.

I'm trying to handle it using object, using the number as key, and the occurrence as value.

const sortNums = (arr) => {
  const result = {}

  for (let i = 0; i < arr.length; i++) {
    const num = result[arr[i]] || 0;
    result[arr[i]] = num + 1;
  }
  //The above will gives me { '1': 2, '2': 4, '3': 3 }

  //How to convert back to array?
}

console.log(sortNums([3,3,2,1,3,2,2,2,1]))

我当然可以使用 Object.entries 映射回数组，但是整个算法将被视为O(n ^ 2)对吗?我正在尝试探索它是否可以在O(n)中实现.还是我不应该使用对象开头?

Of course I can use the Object.entries to map back to an array, but then the entire algorithm will be consider O(n^2) right? I'm trying to explore if it can be achieve in O(n) instead. Or I shouldn't use object to begin with?

推荐答案

您可以获得对数组进行排序的计数.

You could get the count for sorting the array.

const sortNums = array => {
    const count = {};
    for (let v of array) count[v] = (count[v] || 0) + 1;
    return array.sort((a, b) => count[a] - count[b] || a - b);
}

console.log(sortNums([3, 3, 2, 1, 3, 2, 1]));

一种使用对象进行排序的方法.

An approach by using the object for sorting.

const sortNums = array => {
    var count = {},
        result = {};
    for (let v of array) (count[v] = count[v] || []).push(v);
    for (let a of Object.values(count)) (result[a.length] = result[a.length] || []).push(a);
    return Object.values(result).flat(Infinity)
}

console.log(sortNums([3, 3, 2, 1, 3, 2, 1]));

这篇关于如何有效地对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！