Leetcode - 703. Kth Largest Element in a Stream

18387 ワード
leetcode heap テキストリンク

質問する


与えられた配列に値を追加するたびに、配列にk番目に大きな値が返されます.
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]
https://leetcode.com/problems/kth-largest-element-in-a-stream/

解決する


k番目の大きな値は必ずしもmaxheapを使用する必要はありません.この問題ではminheapを使ってこそ簡単に解決できる.
配列をminheapとして作成し、pop heap sizeをkにすると、heapの0番インデックスはkより大きい値を保持します.この性質を利用して解決すればよい.最初はmax heapを使いたいのですが、最初のpopでしか正常値が得られず、その後の値は削除されるので、再度プッシュしなければなりません.ただし、これをminheapに設定して上記の性質を利用すると、以下の操作を実行するだけでこの問題を簡単に解決できます.
まず,配列を最小スタックとして保持し,最大k個(ただし最大値は最小スタック)に達する.
他の値を追加するたびに次の操作が実行される場合、heap[0]は常にk番目に大きい値です.
値
  • がheap[0]より大きい場合、heap[0]をこの値に置き換え、0からheapify down
    • を開始する.
    int kthLargestAdd(KthLargest* obj, int val) { 
    if (obj->heap_size < kth) {
        heap_push(obj, val);
    } else if (val > obj->heap[0]) {
        obj->heap[0] = val;
        heapify_down(obj->heap, 0, obj->heap_size);
    }
    return obj->heap[0];
}
    kthLargestAdd()添加値により、上記特性を維持しながらk個のheapを保持することができる.これは面白い問題です!
    typedef struct {
    int *heap;
    int heap_size;
} KthLargest;
int kth;

void swap(int arr[], int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
void heapify_up(int arr[], int curr_idx)
{
    int p_idx = (curr_idx - 1) / 2;
    
    if (curr_idx < 1)
        return;
    if (arr[curr_idx] < arr[p_idx]) {
        swap(arr, curr_idx, p_idx);
        heapify_up(arr, p_idx);
    }
}

void heap_push(KthLargest* q, int val)
{
    q->heap[q->heap_size] = val;
    q->heap_size++;
    heapify_up(q->heap, q->heap_size - 1);
}

void heapify_down(int arr[], int p_idx, int size)
{
    int min_idx = p_idx;
    int l_idx = p_idx * 2 + 1;
    int r_idx = p_idx * 2 + 2;
    
    if (l_idx < size && arr[l_idx] < arr[min_idx])
        min_idx = l_idx;
    if (r_idx < size && arr[r_idx] < arr[min_idx])
        min_idx = r_idx;
    if (min_idx != p_idx) {
        swap(arr, min_idx, p_idx);
        heapify_down(arr, min_idx, size);
    }
}

int kthLargestAdd(KthLargest* obj, int val);

KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {
    kth = k;
    KthLargest* q = (KthLargest *)malloc(sizeof(KthLargest));
    memset(q, 0, sizeof(KthLargest));
    q->heap = (int *)malloc(sizeof(int) * k);
    memset(q->heap, 0 , sizeof(int) * k);
    
    for (int i = 0; i < numsSize; i++)
        kthLargestAdd(q, nums[i]);
    return q;
}

int kthLargestAdd(KthLargest* obj, int val) { 
    if (obj->heap_size < kth) {
        heap_push(obj, val);
    } else if (val > obj->heap[0]) {
        obj->heap[0] = val;
        heapify_down(obj->heap, 0, obj->heap_size);
    }
    return obj->heap[0];
}

void kthLargestFree(KthLargest* obj) {
    free(obj->heap);    
    free(obj);    
}

/**
 * Your KthLargest struct will be instantiated and called as such:
 * KthLargest* obj = kthLargestCreate(k, nums, numsSize);
 * int param_1 = kthLargestAdd(obj, val);
 
 * kthLargestFree(obj);
*/
    Shellによる導入の自動化
    zmqソース読み取りノートのネットワークメッセージとコマンド