从文件流中读取第K大的数 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int getKthLargest(std::istream &numStream, uint32_t k)
{
    if (!numStream.good())
    {
        throw std::invalid_argument("numStream");
    }
    
    if (k == 0)
    {
        throw std::invalid_argument("k");
    }
    
    try {
        auto initHeap = std::vector<int>(k, INT_MIN);
        std::priority_queue<int, vector<int>, std::greater<int>> minHeap(initHeap.begin(), initHeap.end());
        
        int num;
        while (!numStream.eof())
        {
            numStream >> num;
            if (numStream.fail())
            {
                // bad format number
                continue;
            }
            minHeap.push(num);
            minHeap.pop();
        }
        
        // assume input stream doesn't have any number == INT_MIN
        // to solve this problem, more solid why is adding a counter for input stream
        // but it will raise up another issue, stream length might be overflow.
        // to solve this problem, could stop counting when count == k.
        int result = minHeap.top();
        if (result == INT_MIN)
        {
            // log
        }
        return result;
        
    } catch (exception ex) {
        throw;
    }
}

Comments

Post a Comment