返回第二大的元素index

这题其实就是挖个坑，具体涉及的知识不是很多，需要多想一下
例如fizzbuzz 要先mod 15 再 mod 3 和 5， 只要是做题的逻辑缜密一些，就不会犯错误

新建一个array存元素val + index，然后Quickselect 求第二大元素 = O(n) for both time and space

lc 1509是高频

资深老鼠人 发表于 2021-8-27 07:00
为什么遍历一遍不是o(kn)而是o(n)呢？

因为我没用堆，只用2个变量和2个index处理

不是黑楼主 这个题一遍做对不难的 Facebook这道题是期待你10min以内做完

top K算法也是对的 你这个是top2 时间是
O（N）没问题 只是需要再拿一个数据结构比如array处理下标

更简单就是维护 largest，second Largest，second largest index三个变量

补充内容 (2021-08-28 01:30 +08:00):
应该也需要维护largest index

pipiTu 发表于 2021-8-27 08:11
新建一个array存元素val + index，然后Quickselect 求第二大元素 = O(n) for both time and space

quicksort能到O(n)? 应该是nlgn吧

美帝马甲 发表于 2021-08-27 02:48:55
说topk的人，思路不大对
这题的套路是用largest,second替换，遍历一次即可，时间复杂度是O(n)
2th 和3th都是这个思路

蛤，你可以怼回去说，已知k=2那logk就是O(1)

sakuya9t 发表于 2021-08-27 11:20:03
蛤，你可以怼回去说，已知k=2那logk就是O(1)

严格来说不算top-k。一般top-k是找最大或最小的k个elements，而这里是找一个k-th最小或最大的element。一般用quick select可以做，但也要取决于要求的是average还是worst complexity。另外quick select的代码，如果不是熟记于心的话，短时间内想正确写出来也很有难度。

至于用多个variable来track的方法，实际complexity还是2N, 3N，… kN。当然因为k是constant，也可以简化成N。

jason_pp_weng 发表于 2021-08-27 10:28:16
不是黑楼主 这个题一遍做对不难的 Facebook这道题是期待你10min以内做完

top K算法也是对的 你这个是top2 时间是

这个complexity实质是还是kN，k=2，因为每次你都要检查这两组variables。当要求的k比较大的时候用这种多个variable去记录的方法就不太有效了，generalized方法还是top-k。当然kN的complexity也就是N。

faren753 发表于 2021-08-27 11:40:53
这个complexity实质是还是kN，k=2，因为每次你都要检查这两组variables。当要求的k比较大的时候用这种多个variable去记录的方法就不太有效了，generalized方法还是to

你说的是对的啊 但是和我说的也没矛盾啊

OP问O（N）的算法 这道题topK满足条件

OP又问走一次的算法，topK严格上说不是走一次的 因为要不停的对剩下的区间操作直到剩两个；所以我说的维护四个local var的方法