返回第二大的元素index

莫涯泉水 发表于 2021-8-27 07:27
先遍历一遍找到最大，再遍历一遍找到次大，这样O(N)。这样行么？

非常可。但是有的面试官就会非要你one-pass (无奈

owensy 发表于 2021-8-28 16:44
非常可。但是有的面试官就会非要你one-pass (无奈

我另一个回复放出了one pass的code，不过是想了一段时间才整出来的，放到面试场景下早因紧张而GG了ORZ……

owensy 发表于 2021-8-28 13:44
非常可。但是有的面试官就会非要你one-pass (无奈

我被烙印要求one pass

提供一个C++的解法。Input可以任意大小（比如stream），唯一要求是有足够内存来存output vector。

1. #include <algorithm>  // std::sort
   
2. #include <cmath>      // std::nan
   
3. #include <utility>    // std::pair
   
4. #include <vector>     // std::vector
   
5. 
   
6. // Return the values and indexes of the top-k smallest/largest elements.
   
7. std::vector<std::pair<double, size_t> > FindTopK(
   
8.     const std::vector<double>& input, size_t k, bool is_largest, bool sorted) {
   
9.   // Corner case, return empty vector.
   
10.   if (k == 0) {
    
11.     return std::vector<std::pair<double, size_t> >();
    
12.   }
    
13. 
    
14.   std::vector<std::pair<double, size_t> > result;
    
15.   result.reserve(k);
    
16. 
    
17.   // N iterations (N = input.size()), each iteration is O(k).
    
18.   // Total complexity is O(kN). If k is constant, O(N).
    
19.   for (size_t i = 0; i < input.size(); i++) {
    
20.     double v1 = input[i];
    
21.     if (result.size() < k) {
    
22.       result.emplace_back(v1, i);
    
23.     } else if (is_largest) {
    
24.       // Find top-k largest
    
25.       size_t min_index = 0;  // Local index
    
26.       double min_value = result[0].first;
    
27.       // Complexity of this loop is O(k)
    
28.       for (size_t j = 1; j < k; j++) {
    
29.         double v2 = result[j].first;
    
30.         if (v2 < min_value) {
    
31.           min_index = j;
    
32.           min_value = v2;
    
33.         }
    
34.       }
    
35.       // The new value is larger than the current smallest
    
36.       if (v1 > min_value) {
    
37.         result[min_index] = std::make_pair(v1, i);
    
38.       }
    
39.     } else {
    
40.       // Find top-k smallest
    
41.       size_t max_index = 0;  // Local index
    
42.       double max_value = result[0].first;
    
43.       // Complexity of this loop is O(k)
    
44.       for (size_t j = 1; j < k; j++) {
    
45.         double v2 = result[j].first;
    
46.         if (v2 > max_value) {
    
47.           max_index = j;
    
48.           max_value = v2;
    
49.         }
    
50.       }
    
51.       // The new value is smaller than the current largest
    
52.       if (v1 < max_value) {
    
53.         result[max_index] = std::make_pair(v1, i);
    
54.       }
    
55.     }
    
56.   }
    
57.   if (sorted) {
    
58.     // Complexity of sorting is O(k log k).
    
59.     if (is_largest) {
    
60.       struct {
    
61.         bool operator()(const std::pair<double, size_t>& a,
    
62.                         const std::pair<double, size_t>& b) const {
    
63.           return a.first > b.first;  // Descending order
    
64.         }
    
65.       } comparator;
    
66.       std::sort(result.begin(), result.end(), comparator);
    
67.     } else {
    
68.       struct {
    
69.         bool operator()(const std::pair<double, size_t>& a,
    
70.                         const std::pair<double, size_t>& b) const {
    
71.           return a.first < b.first;  // Ascending order
    
72.         }
    
73.       } comparator;
    
74.       std::sort(result.begin(), result.end(), comparator);
    
75.     }
    
76.   }
    
77.   return result;
    
78. }
    
79. 
    
80. // Return the k-th smallest/largest element and its index.
    
81. // Total complexity O(kN + k). If k is constant, O(N).
    
82. std::pair<double, size_t> FindKthTop(std::vector<double>& input, size_t k,
    
83.                                      bool is_largest) {
    
84.   // Corner case, return something representing invalid.
    
85.   if (k == 0) {
    
86.     return std::make_pair(std::nan(""), static_cast<size_t>(-1));
    
87.   }
    
88. 
    
89.   // O(kN)
    
90.   std::vector<std::pair<double, size_t> > top_k =
    
91.       FindTopK(input, k, is_largest, false);
    
92.   // O(k)
    
93.   if (is_largest) {
    
94.     std::pair<double, size_t> max_pair = top_k[0];
    
95.     for (size_t i = 1; i < k; i++) {
    
96.       std::pair<double, size_t> p = top_k[i];
    
97.       if (p.first > max_pair.first) {
    
98.         max_pair = p;
    
99.       }
    
100.     }
     
101.     return max_pair;
     
102.   } else {
     
103.     std::pair<double, size_t> min_pair = top_k[0];
     
104.     for (size_t i = 1; i < k; i++) {
     
105.       std::pair<double, size_t> p = top_k[i];
     
106.       if (p.first < min_pair.first) {
     
107.         min_pair = p;
     
108.       }
     
109.     }
     
110.     return min_pair;
     
111.   }
     
112. }

复制代码

maristie 发表于 2021-8-28 00:02

补充一点，这个解法逻辑上正确，写法上也基本没错，但是需要考虑两点，即Python里面 set 和 min()/max() 是如何 implement 的。

min()/max()的cost一般是O(N)，linear search。set和dict有些不同。早期版本的CPython内部是用的hashtable，那么amortized cost是O(1)，worst case cost是O(N)。如果implement as min/max heap，那么access cost是O(log N)。面试的时候如果碰见比较较真的面试官可能会问。

darinyu 发表于 2021-08-28 11:54:31
这样不行吧

补充内容 (2021-08-29 03:03 +08:00):

堆保证
1 堆里的两个元素是数组到目前为止的最大的两个，其中堆底是最大，堆顶是次大
2 每一次扫描到新的元素e，只有当e>top是，pop并且把e入堆，这样继续保证新的top次大，新底最大
3 扫描完了把堆顶index输出就是

如果遇到多个相同，看题目要求怎么输出，如果要输出所有，那就拿一个hashmap保存次大的所有index

易潇 发表于 2021-08-27 07:07:16
用2元素最小堆求的话时间复杂度是ON · logK。堆每次插入是logK，判断是否需要pop是1，pop+heapify也是logK

他现在的做法是o(kn)不是更慢..

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

用堆不值得， 能用简单数据结构解决的没必要用复杂数据结构， 有额外成本。

莫涯泉水 发表于 2021-8-27 07:27
先遍历一遍找到最大，再遍历一遍找到次大，这样O(N)。这样行么？

要求one pass

perseids 发表于 2021-8-28 16:17
用堆不值得， 能用简单数据结构解决的没必要用复杂数据结构， 有额外成本。

简单数据结构的代价是效率和可读性，以及必要时候的followup