Open Jocs opened 6 years ago
标题修改记录显示了作者挣扎的内心
@strongcode9527 😆,读得太仔细了哈,关注重点。
跳过你的代码部分,快糙猛地实现了一个,直接n * (n - 1)次比较 🤣
function sort (queue) {
let swap
for (let i = 0; i < queue.length; i++) {
swap = queue.shift()
for (let j = 0; j < queue.length; j++) {
if (swap > queue[0]) {
queue.push(queue.shift())
} else {
queue.push(swap)
swap = queue.shift()
}
}
queue.push(swap)
}
return queue
}
跟你的实现差不多,没优化
有趣的题目也可以分享到 https://github.com/eleme/rice/issues 大家一起玩
@myst729 👌,我把题目整理下,再发上去。
又是十点钟才离开公司,拖着疲惫的驱壳,挪着步子,走进地铁站,上海真的很多人,晚上十点多了,地铁上还是很挤,我习惯的拿出了手机,看一下微信群,放松下加班后劳累的身体。
打开了小区业主群,一个叫做「九哥哥」的邻居在小区群里竟然提了一个问题,准确的说是一道算法题:
哎,本来想放松下心情的,结果又被这道算法题勾起了兴趣。。。脑子里迅速浮现了常见的排序算法:冒泡排序、快速排序、插入排序、归并排序。。。
果然,群里马上就炸开锅了(感觉我们业主群整个就是一个 IT 交流互助群了),迅速有一位「小毛」的业主回复了。
「unix」的业主跟着回复道:
想想也就知道了,队列(FIFO)只提供了 pop(从队列末端推出元素)和 unshift(从队列入口推入元素),而且只有一个额外的空间用于暂存元素,因此根本就没法交换两个来冒泡排序。
后面果然有人反驳道了。
这时候,作为群主的「小毛」不服气了。怒怼众人。
终于来了一个反对冒泡排序,有理有据的回答了。
看来,冒泡排序已经被大家否决了,但是群里又抛出了另外一个疑问?
讨论到这里,感觉,终于有人给出了文字描述的算法。
感觉算法已经基本有了,群里疑问又一次升级。。。讨论到了算法复杂度的层面了。。。
聊天看到这儿才发现,这原来不是面试题。。。是用算法解决实际问题啦。
👌,感觉聊天到这儿已经接近尾声,在地铁上无聊,也没心思去想它,开始打游戏了。回到家,蹭着脑袋清醒多了,打开电脑,写下了如下实现算法:
算法不复杂,嵌套两个循环,如果以代码中
x > peak(list)
比较作为最耗时的步骤,假设队列长度为 n,那么总共需要做 (n - 1) * n / 2 次比较。可见其时间复杂度为 O(n2)。😝,感觉小群业主群已然变味了,不再讨论菜米油盐,也不再抱怨小区物业无作为。感觉聊天内容到了一个新的高度。竟然聊计算机算法了,这么稀奇的事情,我决定把它记下来。
写在最后,也没见「小毛」用冒泡排序写出实现代码来,当然也就没人吃屎了。