返回第二大的元素index

不吹不黑
现场编程
今天店面居然遇到这题
开始以为很简单，写了个直接赋值的
   if(nums[i]>largest){

            }else if(nums[i]>second){
结果烙印一笑，我立马**
给了个 test case: int[] nums3={6,6,1,6,5,3,5,2,1,3};
让我run

然后烙印和我一起在intellij下debug
然后在烙印指导下把程序写完了

纯好奇， 这题要没刷过，有多少人能现场bug free
要求O(n），一次遍历就找到index

如果要求一次遍历，这样应该行(用[1,2,3]的6种组合试了都过)：

1. def findSecond(a):
   
2.     largest = float('-inf')
   
3.     second = float('-inf')
   
4.     idx_l, idx_s = 0, 0
   
5.     for idx, val in enumerate(a):
   
6.         if val > largest:
   
7.             second, idx_s = largest, idx_l
   
8.             largest, idx_l = val, idx
   
9.         elif val > second and val != largest:
   
10.             second, idx_s = val, idx
    
11.     return idx_s

复制代码

这种top-k in N的题，如果k很接近N而且N不是特别大，可以直接全部排序，complexity是N log N。如果k比较小或者N特别大，那么只要存一个大小为k的container，每次替换k里面最大或者最小的一个（linear search），那么整体complexity是kN。如果最后需要排序，那么再加上k log k即可。

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

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

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

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

这个用一个两元素最小堆不是更简单…

我能 zszszszszszszszs

说topk的人，思路不大对
这题的套路是用largest,second替换，遍历一次即可，时间复杂度是O(n)
2th 和3th都是这个思路

已经想歪了
烙印还行，还耐心给你引导。

有的面试官抓住这种问题fail你


补充内容 (2021-08-27 23:40 +8:00):
加一句 是 我想歪了
没有说楼主哈

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

为什么遍历一遍不是o(kn)而是o(n)呢？

用2元素最小堆求的话时间复杂度是ON · logK。堆每次插入是logK，判断是否需要pop是1，pop+heapify也是logK

先遍历一遍找到最大，再遍历一遍找到次大，这样O(N)。这样行么？