我有一个项目列表，我希望它们根据字段enqueuedAt降序排列。在属于同一队列（由 标识）的项目中queueName，position（最低的第一个）应优先于enqueuedAt。换句话说，整体排序顺序应该基于enqueuedAt（降序），并且在内部，属于同一队列的项目之间互换位置，以便具有较低的项目position始终排在具有较高的项目之前position。为了实现这一目标，我想出了下面的代码。有没有办法提高时间复杂度？const data = [ { id: 1, enqueuedAt: 8, queueName: 'Queue 1', position: 1 }, { id: 2, enqueuedAt: 7, queueName: 'Queue 2', position: 1 }, { id: 3, enqueuedAt: 6, queueName: 'Queue 3', position: 3 }, { id: 4, enqueuedAt: 5, queueName: 'Queue 4', position: 2 }, { id: 5, enqueuedAt: 1, queueName: 'Queue 1', position: 2 }, { id: 6, enqueuedAt: 2, queueName: 'Queue 4', position: 1 }, { id: 7, enqueuedAt: 4, queueName: 'Queue 1', position: 3 }, { id: 8, enqueuedAt: 3, queueName: 'Queue 2', position: 2 }]function sortThem(array) { array.sort((a, b) => b.enqueuedAt - a.enqueuedAt) for (let i = 0; i < array.length - 1; i++) { for (let j = i + 1; j < array.length; j++) { if (array[i].queueName === array[j].queueName) { if (array[j].position < array[i].position) { const t = array[j] array[j] = array[i] array[i] = t } } } } return array}console.log(sortThem(data))
3 回答
幕布斯7119047
TA贡献1794条经验 获得超8个赞
一个简短的方法可以
对数据进行排序
enqueuedAt，分组依据
queueName,将数组减少
对任何组进行排序
position，获取临时结果数组中同一索引处的所有项目，最后
采取平面阵列。
const
data = [{ id: 1, enqueuedAt: 8, queueName: 'Queue 1', position: 1 }, { id: 2, enqueuedAt: 7, queueName: 'Queue 2', position: 1 }, { id: 3, enqueuedAt: 6, queueName: 'Queue 3', position: 3 }, { id: 4, enqueuedAt: 5, queueName: 'Queue 4', position: 2 }, { id: 5, enqueuedAt: 1, queueName: 'Queue 1', position: 2 }, { id: 6, enqueuedAt: 2, queueName: 'Queue 4', position: 1 }, { id: 7, enqueuedAt: 4, queueName: 'Queue 1', position: 3 }, { id: 8, enqueuedAt: 3, queueName: 'Queue 2', position: 2 }],
result = Object
.values(data
.sort((a, b) => b.enqueuedAt - a.enqueuedAt)
.reduce((r, o) => ((r[o.queueName] ??= []).push(o), r), {})
)
.reduce((r, array) => (array
.sort((a, b) => a.position - b.position)
.forEach((o, i) => (r[i] ??= []).push(o)),
r
), [])
.flat();
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
慕勒3428872
TA贡献1848条经验 获得超6个赞
我不认为你的代码产生的结果应该优先于queuedAt它应该产生的结果。您的算法首先对以queuedAt错误位置顺序出现的元素进行排序，然后交换出现位置顺序的元素，但这并不总是导致尽可能优先的顺序queuedAt。
例如，在您的输出中，元素 withqueuedAt=3出现在元素 with之后queuedAt=2，但它们没有理由不能以相反的顺序出现：当它们属于同一队列时，调整后的排序仍会按其位置顺序列出项目，但会优先考虑更大的queuedAt值。
建议的算法
为了纠正这个缺点并获得更好的时间复杂度，您可以使用最大堆。该堆中的一个条目将对应于一个队列，其所有元素均按 排序position。堆使用的键是队列第一个元素的属性，即具有最小值的元素。queuedAtposition
然后，您将从堆中选择顶部条目（队列），从该队列中提取第一个元素，并将其推送到最终结果。如果队列尚未为空，则将其保留在堆上，但调整其key，因此它再次对应于queuedAt现在第一个（least position）的队列元素的属性。如果队列已耗尽，则将其从堆中删除。如果您继续这样做直到堆被清空，您将按照所需的顺序访问条目。
不幸的是，JavaScript 没有本机堆实现。所以你必须扔掉你自己的，或者包括一个库（有几个）。
在下面的实现中，我选择以相反的顺序对队列进行排序，因此我可以按所需的顺序弹出元素。
开始了：
/* MinHeap minimised - taken from https://stackoverflow.com/a/66511107/5459839 */
const MaxHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]<h[j+1][0])j++;if(j>=h.length||k>=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k>h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};
// Main function
function customSort(data) {
// Create a map with a key for each queue
let map = new Map(data.map(o => [o.queueName, []]));
// Populate the map entries
for (let o of data) map.get(o.queueName).push(o);
// We have no more need of the Map:
let queues = [...map.values()];
// Sort each queue by descending position (so we can pop from those queues in ascending order)
for (let queue of queues) queue.sort((a, b) => b.position - a.position);
// Build a heap of pairs, where first value in pair is the heap key, and the second is the payload (the queue)
let heap = MaxHeap.heapify(queues.map(queue => [queue[queue.length - 1].enqueuedAt, queue]));
let result = [];
while (heap.length) {
// Peek in the heap, to get the "top" queue
let queue = heap[0][1];
// Extract the element from that queue with the lowest position
result.push(queue.pop());
if (queue.length) {
// Adapt the key of this queue on the heap
MaxHeap.exchange(heap, [queue[queue.length - 1].enqueuedAt, queue]);
} else {
// Remove the now empty queue from the heap
MaxHeap.pop(heap);
}
}
return result;
}
// Example data from the question:
const data = [{id: 1,enqueuedAt: 8,queueName: 'Queue 1',position: 1},{id: 2,enqueuedAt: 7,queueName: 'Queue 2',position: 1},{id: 3,enqueuedAt: 6,queueName: 'Queue 3',position: 3},{id: 4,enqueuedAt: 5,queueName: 'Queue 4',position: 2},{id: 5,enqueuedAt: 1,queueName: 'Queue 1',position: 2},{id: 6,enqueuedAt: 2,queueName: 'Queue 4',position: 1},{id: 7,enqueuedAt: 4,queueName: 'Queue 1',position: 3},{id: 8,enqueuedAt: 3,queueName: 'Queue 2',position: 2}]
console.log(customSort(data));
时间复杂度为O(nlogn)，就像普通的基于比较的排序一样
没有堆的解决方案
可以在不使用堆的情况下在 JavaScript 中实现此操作，但它需要requiredAt范围有限（但它仍然是一个很大的范围： 2 32）：我们可以利用 JavaScript 在普通情况下保证的关键迭代顺序自2017-2020 年语言规范更新以来的对象。
堆中的requiredAt键在哪里，它可以成为普通对象中的键。由于您需要降序排列，我们必须应用requiredAt到可以按升序迭代的正整数的映射。映射可以类似于：32000 - requiredAt。
下面是如何编码：
function customSort(data) {
// Create a map with a key for each queue
let map = new Map(data.map(o => [o.queueName, []]));
// Populate the map entries
for (let o of data) map.get(o.queueName).push(o);
// We have no more need of the Map:
let queues = [...map.values()];
// Sort each queue by descending position (so we can pop from those queues in ascending order)
for (let queue of queues) queue.sort((a, b) => b.position - a.position);
// Build an object keyed by "negative" `queuedAt`
const MAX = 2 ** 31 - 1;
let sorted = Object.fromEntries(queues.map(queue => [MAX - queue[queue.length - 1].enqueuedAt, queue]));
let result = [];
for (let i = 0; i < data.length; i++) {
// Use JS behaviour where index keys are iterated in numerical order
let queuedAt;
for (queuedAt in sorted) break;
// Get the queue at this (first) key and remove the entry
let queue = sorted[queuedAt];
delete sorted[queuedAt];
// Extract the element from that queue with the lowest position
result.push(queue.pop());
if (queue.length) {
// Store the shortened queue at its new key
sorted[MAX - queue[queue.length - 1].enqueuedAt] = queue;
}
}
return result;
}
// Example data from the question:
const data = [{id: 1,enqueuedAt: 8,queueName: 'Queue 1',position: 1},{id: 2,enqueuedAt: 7,queueName: 'Queue 2',position: 1},{id: 3,enqueuedAt: 6,queueName: 'Queue 3',position: 3},{id: 4,enqueuedAt: 5,queueName: 'Queue 4',position: 2},{id: 5,enqueuedAt: 1,queueName: 'Queue 1',position: 2},{id: 6,enqueuedAt: 2,queueName: 'Queue 4',position: 1},{id: 7,enqueuedAt: 4,queueName: 'Queue 1',position: 3},{id: 8,enqueuedAt: 3,queueName: 'Queue 2',position: 2}]
console.log(customSort(data));
最后的评论
请注意顺序与您的输出有何不同，但仍然符合您设定的规则。该解决方案中的顺序确实最大化了 的优先级enqueuedAt。
神不在的星期二
TA贡献1963条经验 获得超6个赞
const data = [
{
id: 1,
enqueuedAt: 8,
queueName: 'Queue 1',
position: 1
},
{
id: 2,
enqueuedAt: 7,
queueName: 'Queue 2',
position: 1
},
{
id: 3,
enqueuedAt: 6,
queueName: 'Queue 3',
position: 3
},
{
id: 4,
enqueuedAt: 5,
queueName: 'Queue 4',
position: 2
},
{
id: 5,
enqueuedAt: 1,
queueName: 'Queue 1',
position: 2
},
{
id: 6,
enqueuedAt: 2,
queueName: 'Queue 4',
position: 1
},
{
id: 7,
enqueuedAt: 4,
queueName: 'Queue 1',
position: 3
},
{
id: 8,
enqueuedAt: 3,
queueName: 'Queue 2',
position: 2
}
]
function sortThem(array) {
const grouped = {}
const sorted = []
array.forEach(n => {
if (!grouped[n.queueName]) {
grouped[n.queueName] = [n];
return;
}
grouped[n.queueName] = [...grouped[n.queueName], n]
})
Object.keys(grouped).forEach(n => {
const sort = grouped[n].sort((a, b) => b.enqueuedAt - a.enqueuedAt)
sorted.push(...sort);
})
return sorted
}
console.log(sortThem(data))
像这样的事情是可行的，首先按队列名称对项目进行分组，然后对每个组进行排序并将它们推回到数组中。您可能还需要按队列名称排序，因为我认为它在本示例中有效，因为队列名称已经处于正确的顺序。
添加回答
举报
0/150
提交
取消