返回第二大的元素index

Shubin_ren 发表于 2021-8-28 16:31
简单数据结构的代价是效率和可读性，以及必要时候的followup

这题就是4个local vairable 代替一个Priority Queue， 牺牲了啥可读性？ 效率肯定是提高不是牺牲。

perseids 发表于 2021-8-28 16:57
这题就是4个local vairable 代替一个Priority Queue， 牺牲了啥可读性？ 效率肯定是提高不是牺牲。

可读性不是local variable多少的问题
你的逻辑上相当于是一种穷举的做法，一个个去比较现在在variable里面的两个值，堆实际上是把这个过程分成两个独立的子过程，1 是判断，新element 和现有最小的 2是排序，在代码的角度这两个东西可以分别封装扩展
效率上，k 和 lgK，这就是你所谓的提升？

Shubin_ren 发表于 2021-8-28 17:01
可读性不是local variable多少的问题
你的逻辑上相当于是一种穷举的做法，一个个去比较现在在variable里 ...

建议你看一下Priority Queue的实现源码。

perseids 发表于 2021-8-28 17:04
建议你看一下Priority Queue的实现源码。

你硬要这样和stl比，那可以自己实现一个简化版的heap
if(e > second) {
   swap(e, second);
   if(second > first) {
      swap(first, second);
    }
}

这段可以独立出来扩展到k，无非是自己决策如何实现这个“heap”，而不是变成穷举或者冒泡的思路
   

wisdompeak2 发表于 2021-8-27 02:09
我能 zszszszszszszszs

捉大佬！

perseids 发表于 2021-8-28 19:17
要求one pass

我另一个回复是one pass，应该行？

Shubin_ren 发表于 2021-08-28 15:22:56
堆保证
1 堆里的两个元素是数组到目前为止的最大的两个，其中堆底是最大，堆顶是次大
2 每一次扫描到新的元素e，只有当e>top是，pop并且把e入堆，这样继续保证新的top次大，新底最大

1)  真的吗？  这是怎么实现的  (我真的不知道还有这个feature  能不能给个reference?
2)  那如果当前堆里面是 10,  5  现在来了一个8   这个8也没法pop顶上的  也不能把第二个pop  那怎么办？

darinyu 发表于 2021-08-29 10:05:24
1)  真的吗？  这是怎么实现的  (我真的不知道还有这个feature  能不能给个reference?
2)  那如果当前堆里面是 10,  5  现在来了一个8   这个8也没法pop顶上的

哥们，我觉得你很有必要看一下堆的基础知识

https://zh.m.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D

Shubin_ren 发表于 2021-08-29 11:25:52
哥们，我觉得你很有必要看一下堆的基础知识

https://zh.m.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D

这个ref里面 堆的两个性质

1.任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
2.堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

哪个能保证次大的位置？

然后我那个例子你还怎么解决  我还是没懂

darinyu 发表于 2021-08-29 11:34:23
这个ref里面 堆的两个性质

1.任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。

你还是没看懂堆是干嘛的啊
你的例子
堆里面是10和5，其中10在底，5在顶
8>5，所以5出堆，8 push进去
然后就10在底8在顶，ref里面例程你看了吗？？