Leetcode - 2099. Find Subsequence of Length K With the Largest Sum

質問する

与えられた配列では、k個のサブシーケンスのうちのそれらと最大の組合せが出力される.既存のシナリオの順序は変更できません.

Input: nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
Explanation: 
The subsequence has the largest sum of -1 + 3 + 4 = 6.

https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/

解決O(K*N)

配列中の最大k個の出力は典型的に時間複雑度O(N)+O(k logn)で解決されるスタック問題であり,この問題には既存のインデックス順序を変えることができないという条件がある.この部分でO(KN)となり、最悪の場合はO(N^2)になる可能性があります.
まず前回解決した方式でk個のminheapを残す方式で解決する.残りのk個のheap配列は最大のサブシーケンスである.しかし,順序は所与の配列のindex順序ではないので,それを並べ替えるためにO(K*N)となる.add_num以降、ソートされた部分は以下のようになり、最悪の場合はO(N^2)となる可能性があります.とても気に入らないハーモニー

    for (int i = 0; i < numsSize; i++) // O(N * logN)
        add_num(q->heap, q->heap_size, nums[i], i);
        
    for (int n = 0; n < numsSize; n++) {
        for (int i = 0; i < k; i++) {
            int cidx = q->heap[i].idx;
            if (n == cidx)
                ret[retcnt++] = nums[cidx]; // FIXME: idx 순서
        }
    }
    return ret;

解決O(K logn)

上の位置合わせを改善します.kと同じheapを構築した後,idx値に基づいてminheapifyを行った.popの値はret[]に順次保存されます.heapify O(N)、pop O(k logN).最悪の場合O(Nlogn)heapify_downパラメータで関数ポインタを渡すのも見どころです.

    for (int i = 0; i < numsSize; i++) // O(N * logN)
        add_num(q->heap, q->heap_size, nums[i], i);
    
    build_heap(q->heap, q->heap_size, compare_idx); // O(N)
    for (int i = 0; i < k; i++) // O(K * logN)
        ret[i] = heap_pop(q->heap, compare_idx).val;
    return ret;

送信結果は次のとおりです.
Runtime: 7 ms, faster than 93.10%
Memory Usage: 7.1 MB, less than 48.28%

完全なソースコード

struct elem {
    int idx;
    int val;
};

struct pq {
    int heap_size;
    struct elem *heap;
};
struct pq *q;
int g_k;

void swap(struct elem arr[], int a, int b)
{
    struct elem temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void heapify_up(struct elem arr[], int curr_idx)
{
    int p_idx = (curr_idx - 1) / 2;
    
    if (curr_idx < 1)
        return;
    if (arr[curr_idx].val < arr[p_idx].val) {
        swap(arr, curr_idx, p_idx);
        heapify_up(arr, p_idx);
    }
}

void heap_push(struct elem arr[], int val, int idx)
{
    arr[q->heap_size].val = val;
    arr[q->heap_size].idx = idx;
    q->heap_size++;
    heapify_up(arr, q->heap_size - 1);
}

bool compare_val(struct elem a, struct elem b)
{
    if (a.val < b.val)
        return true;
    else
        return false;
}

bool compare_idx(struct elem a, struct elem b)
{
    if (a.idx < b.idx)
        return true;
    else
        return false;
}

void heapify_down(struct elem arr[], int p_idx, int size, bool (*cmp)(struct elem, struct elem))
{
    int min_idx = p_idx;
    int l_idx = p_idx * 2 + 1;
    int r_idx = p_idx * 2 + 2;
    
    if (l_idx < size && cmp(arr[l_idx], arr[min_idx]))
        min_idx = l_idx;
    if (r_idx < size && cmp(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, cmp);
    }
}

void build_heap(struct elem arr[], int size, bool (*cmp)(struct elem, struct elem))
{
    for (int i = (size / 2) - 1; i >= 0; i--)
        heapify_down(arr, i, size, cmp);
}

struct elem heap_pop(struct elem arr[], bool (*cmp)(struct elem, struct elem))
{
    struct elem ret = arr[0];
    swap(arr, 0, q->heap_size -1);
    q->heap_size--;
    heapify_down(arr, 0, q->heap_size, cmp);
    return ret;
}

void add_num(struct elem arr[], int size, int val, int idx)
{
    if (size < g_k) {
        heap_push(arr, val, idx);
    } else if (val > arr[0].val) {
        arr[0].val = val;
        arr[0].idx = idx;
        heapify_down(arr, 0, size, compare_val);
    }
}

// max heap -> heapify - heapify O(N) / pop O(K * logN) 
// min heap with k size - insert O(N*logN) / pop O(K)
int* maxSubsequence(int* nums, int numsSize, int k, int* returnSize){
    q = (struct pq *)malloc(sizeof(struct pq));
    memset(q, 0, sizeof(struct pq));
    q->heap = (struct elem *)malloc(sizeof(struct elem) * k);
    memset(q->heap, 0, sizeof(struct elem) * k);
    *returnSize = k;
    int *ret = (int *)malloc(sizeof(int) * k);
    g_k = k;
    
    for (int i = 0; i < numsSize; i++) // O(N * logN)
        add_num(q->heap, q->heap_size, nums[i], i);
    
    build_heap(q->heap, q->heap_size, compare_idx); // O(N)
    for (int i = 0; i < k; i++) // O(K * logN)
        ret[i] = heap_pop(q->heap, compare_idx).val;
    return ret;
}