典型的topk问题

想到第k大元素, 很明显就是topk问题
第k大就是要利用堆的特性

思路

维护一个k大小的最小堆, 然后把剩下的元素依次与堆顶进行比较, 如果大于堆顶就舍弃堆顶元素把更大的元素作为新堆顶, 然后向下调整维护堆的性质
时间复制度, 建堆 (k/2)log(k) , 维护第k大, (n-k)log(k), 最终时间复杂度 = O(nlog(k))
这个题中是第三大的元素, 所以k = 3

代码

Golang

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var heap []int
var heapCap, heapSize = 0, 3

func main() {
    var num int
    heapSize = 3
    sc := bufio.NewScanner(os.Stdin)
    sc.Scan()
    str := sc.Text()
    heap = append(heap, 0)
    for _, numstr := range strings.Split(str[1:len(str)-1], ",") {
        num, _ = strconv.Atoi(numstr)
        heap = append(heap, num)
    }
    heapCap = len(heap) - 1
    makeHeap(heapSize)
    getTopK(heapSize)
    fmt.Println(heap[1])
}
// heapSize
func siftDown(i int) {
    var tmp int
    for i*2 <= heapSize {
        if heap[i] > heap[i*2] {
            tmp = i*2
        }else{
            tmp = i
        }
        if i*2+1 <= heapSize {
            if heap[tmp] > heap[i*2+1] {
                tmp = i*2+1
            }
        }
        if tmp != i {
            swap(tmp, i)
            i = tmp
        }else{
            break
        }
    }
}

func siftUp(tmp int) {
    for tmp != 1 {
        if heap[tmp] < heap[tmp/2] {
            swap(tmp, tmp/2)
        }
        tmp /= 2
    }
}

func makeHeap(size int) {
    for i := size; i > size/2; i-- {
        siftUp(i)
    }
}

func swap(a, b int) {
    heap[a], heap[b] = heap[b], heap[a]
}

func getTopK(k int) {
    for i:=k+1; i <= heapCap; i++ {
        if heap[i] > heap[1] {
            heap[1] = heap[i]
            siftDown(1)
        }
    }
}

Cpp

#include <bits/stdc++.h>

#define  ends " "
using namespace std;
int h[101] = {0};

int main() {
    int num = 0, k = 3;
    priority_queue<int, vector<int>, greater<int> > mHeap;
    while (getchar() != ']') {
        cin >> h[num++];
    }
    for(int i=0;i<k;i++) {
        mHeap.push(h[i]);
    }
    for(int i=k;i<num;i++){
        if (h[i]>mHeap.top()) {
            mHeap.pop();
            mHeap.push(h[i]);
        }
    }
    cout << mHeap.top() << endl;
    return 0;
}