返回第二大的元素index

1. """
   
2. Find indices in ascending order whose values are second largest in arr in O(n) time and space.
   
3. 
   
4. >>> find_second_largest_elements([6,6,1,6,5,3,5,2,1,3])
   
5. [4, 6]
   
6. """
   
7. 
   
8. from typing import List
   
9. from collections import defaultdict
   
10. 
    
11. def find_second_largest_elements(arr: List[int]) -> List[int]:
    
12.     max2, indices = set(), defaultdict(list)
    
13.     for i, e in enumerate(arr):
    
14.         indices[e].append(i)
    
15.         if not max2 or len(max2) < 2:
    
16.             max2.add(e)
    
17.         else:
    
18.             if e > min(max2):
    
19.                 max2.remove(min(max2))
    
20.                 max2.add(e)
    
21.     return indices[min(max2)]
    
22. 
    
23. if __name__ == '__main__':
    
24.     import doctest
    
25.     doctest.testmod()

复制代码

可以 看了大家的方法 我学到很多

美帝马甲 发表于 2021-08-27 09:41:05
因为我没用堆，只用2个变量和2个index处理

如果求第三大，不就需要3个了吗？这里只是k=2的特例吧。

资深老鼠人 发表于 2021-8-28 02:43
如果求第三大，不就需要3个了吗？这里只是k=2的特例吧。

yes
2th和3th的一次遍历思路类似
我遇到过面3th的，也是要求一次遍历

1. package ThirdReplace;
   
2. 
   
3. public class findSecondMaxIndex {
   
4.     int findSecondIndex(int[] nums){
   
5. 
   
6.         int largest=Integer.MIN_VALUE,second=Integer.MIN_VALUE;
   
7.         int  largestIdx=0,res=0;
   
8.         for(int i=0;i<nums.length;i++){
   
9.             if(nums[i]>largest){
   
10.                 second=largest;
    
11.                 res=largestIdx;
    
12.                 largest=nums[i];
    
13.                 largestIdx=i;
    
14.             }else if(nums[i]>second && largest!=nums[i]){
    
15.                 second=nums[i];
    
16.                 res=i;
    
17.             }
    
18.         }
    
19. 
    
20.         return res;
    
21.     }
    
22. 
    
23.     public static void main(String[] args){
    
24.         int[] nums1={1,4,3};
    
25.         int[] nums2={5,4,4,3,2,5,0};
    
26.         int[] nums3={6,6,1,6,5,3,5,2,1,3};
    
27.         int[] nums4={3,4,1};
    
28.         findSecondMaxIndex test=new findSecondMaxIndex();
    
29.         System.out.println(test.findSecondIndex(nums1)==2);
    
30.         System.out.println(test.findSecondIndex(nums2)==1);
    
31.         System.out.println(test.findSecondIndex(nums3)==4);
    
32.         System.out.println(test.findSecondIndex(nums4)==0);
    
33.     }
    
34. }
    

复制代码

放下我的最终code

美帝马甲 发表于 2021-8-28 09:59
放下我的最终code

挺牛的 感觉我一时半会写不出这种

Shubin_ren 发表于 2021-08-26 17:52:25
这个用一个两元素最小堆不是更简单…

这样不行吧

补充内容 (2021-08-29 03:03 +08:00):
两元素最小堆只能保证第一个最小没法保证第二个次小

第二个条件加个小于largest不就好了？

美帝马甲 发表于 2021-08-28 09:59:34
package ThirdReplace;

public class findSecondMaxIndex {

这样还是2N啊，跟用一个array没区别。假如input就是一个单调递增的array，那么每次你都要把所有的variables都往后shift一位，然后再update最大那个。如果是找第k大的那个element，那么你需要2k个variables，每个iteration要shift 2k-2次加上update最大那个，所以每次iteration的cost还是k，总共仍然是kN。

其实这个题的通用形式就是input size N，find the k-th/top-k min/max element(s)，其中N和k都是变量。解法基本是一样的，只不过当给定k是constant且比较小的时候，会有更简单的写法，但是无法降低complexity（除非有其它条件，比如input是排序好的）。

这道题到底难点在哪儿啊？LZ是没有考虑到element可能相等的情况嘛？相同element的index存个list不就行了吗？