题解 | #设计LFU缓存结构#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * lfu design
 * @param operators int整型二维数组 ops
 * @param operatorsRowLen int operators数组行数
 * @param operatorsColLen int* operators数组列数
 * @param k int整型 the k
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
#include <stdio.h>
#include <stdlib.h>

int* LFU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) {
    // write code here
    int *a = (int*)malloc(sizeof(int) * operatorsRowLen);
    int **t = (int**)malloc(sizeof(int*) * k);
    for(int i = 0; i < k; i++) {
        t[i] = (int*)malloc(sizeof(int) * 4);
        t[i][0] = 0;
        t[i][1] = 0;
        t[i][2] = 0;
        t[i][3] = 0;
    }
    int alen = 0;
    for(int i = 0; i < operatorsRowLen; i++) {
        char set = 0;
        if(operators[i][0] == 1) {
            for(int j = 0; j < k; j++) {
                if(t[j][1] == operators[i][1]) {
                    t[j][2] = operators[i][2];
                    t[j][0]++;
                    t[j][3] = i;
                    set = 1;
                    break;
                }
            }
            if(set == 0) {
                int min = 10000;
                int p;
                for(int j = 0; j < k; j++) {
                    if(t[j][0] < min) {
                        min = t[j][0];
                        p = j;
                    } else if(t[j][0] == min && t[j][3] < t[p][3]) {
                        min = t[j][0];
                        p = j;
                    }
                }
                t[p][1] = operators[i][1];
                t[p][2] = operators[i][2];
                t[p][0] = 1;
                t[p][3] = i;
            }
        } else {
            for(int j = 0; j < k; j++) {
                if(t[j][1] == operators[i][1]) {
                    a[alen++] = t[j][2];
                    t[j][0]++;
                    t[j][3] = i;
                    set = 1;
                    break;
                }
            }
            if(set == 0) a[alen++] = -1;
        }
    }
    *returnSize = alen;
    return a;
}